Question

An array \( A \) of length \( n \) with distinct elements is said to be bitonic if there is an index \( 1 \leq i \leq 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 \)?

• A. \(\Theta(n)\)
• B. \(\Theta(1)\)
• C. \(\Theta(\log^2 n)\)
• D. \(\Theta(\log n)\)

Hint:

{Binary search is a powerful technique that reduces search complexity from \( O(n) \) to \( O(\log n) \) in structured data.}

Answer 1

The Correct Option is D

- A bitonic array consists of an increasing and a decreasing sequence. A bitonic array first increases and then decreases. This structure allows efficient algorithms for finding the peak element, as the peak is the largest element where the increasing sequence changes to the decreasing one.
- We can find the peak element using \( \Theta(\log n) \) comparisons with binary search. Since the array is bitonic, we can use a modified binary search to find the peak in \( \Theta(\log n) \) time. The key observation is that the middle element of the array either has a larger neighbor or it is the peak.
- After locating the peak, two separate binary searches on each half take \( \Theta(\log n) \) time. Once the peak is identified, we perform binary searches on both halves of the array (one for the increasing part and one for the decreasing part), which each take \( \Theta(\log n) \) time.
- Thus, the total worst-case time complexity is \( \Theta(\log n) \). The binary search steps, both for finding the peak and searching each half, each take logarithmic time, so the overall time complexity is dominated by \( \Theta(\log n) \).
Thus, the correct option is (D).