سوال ۵۷ کنکور ارشد مهندسی کامپیوتر ۱۴۰۴

A bitonic sequence is one that, read around a circle, consists of exactly one ascending run followed by one descending run. Equivalently, it is the concatenation of a non-decreasing run and a non-increasing run. The key observation is that such a sequence is essentially two already-sorted lists glued together, so we never need a full comparison sort.

Algorithm (linear time):

1. Scan the array once to find the peak (the single point where the sequence stops ascending and starts descending). This is $O(n)$.
2. The peak splits $A$ into an ascending prefix and a descending suffix. Reverse the descending suffix (or read it back-to-front) so you have two sorted runs.
3. Merge the two sorted runs with a single linear pass, exactly like the merge step of merge sort. This is $O(n)$.

Total cost:

$O(n) + O(n) = O(n).$

Why the other options are not the best time:

• $O(n\log n)$ is what a general comparison sort (merge/heap/quick) costs, but it ignores the bitonic structure.
• $O(n^{2})$ and $O(n\sqrt{n})$ are even slower and unnecessary.

Because a comparison-based sort needs $\Omega(n)$ just to read the input, $O(n)$ is also optimal here — the bitonic property removes the $\log n$ factor.

Exam trick: A bitonic (or any "sorted then reversed-sorted") sequence is the merge of two monotone runs, so it sorts in linear $O(n)$ time — no need to pay the general $\Theta(n\log n)$ comparison-sort bound.