حل تشریحی سوال شماره 39 دروس مشترک

آرایه‌ای به طول n از اعداد صحیح متمایز داده شده است. می‌دانیم به ازای یک اندیس $\left(n\ge k\ge 1\right)k$ عناصر آرایه از خانه 1 تا k به‌صورت صعودی و از خانه k تا n به‌صورت نزولی هستند. اگر بخواهیم بزرگ‌ترین عدد ذخیره شده در آرایه را بیابیم، بهترین پیچیدگی زمانی الگوریتم کدام یک از گزینه‌های زیر است؟ (فرض کنید k برای الگوریتم از قبل مشخص نیست.)