An array A of length n with distinct elements is said to be bitonic if there is an index 1 ≤ i ≤ n such that A[1..i] is sorted in the non-decreasing order and A[i + 1..n] is sorted in the non-increasing order.

Which ONE of the following represents the best possible asymptotic bound for th

Question

An array A of length n with distinct elements is said to be bitonic if there is an index 1 ≤ i ≤ n such that A[1..i] is sorted in the non-decreasing order and A[i + 1..n] is sorted in the non-increasing order.

Which ONE of the following represents the best possible asymptotic bound for the worst-case number of comparisons by an algorithm that searches for an element in a bitonic array A?

Accepted Answer

Θ(log n). The correct option is Θ(log n) because a bitonic array can be efficiently searched using a modified binary search approach. This method allows us to find the peak element in logarithmic time, and then we can perform binary searches on the two sorted halves, resulting in an overall search time of Θ(log n).

Solution

Related GATE Technical questions