An array 𝐴 of length 𝑛 with distinct elements is said to be bitonic if there…

Answer: Θ(log n).

Reasoning (high level): find the peak element using binary search, then binary-search for the target in the increasing side and in the decreasing side.

• Find the peak (index of the maximum) in O(log n): at each step check A[mid] and A[mid+1]; if A[mid] < A[mid+1] the peak is to the right, otherwise it is to the left. This halves the search interval each time.

• Binary-search the increasing subarray [1..peak] for the target in O(log n): use standard binary search comparisons because this part is sorted in non-decreasing order.

• Binary-search the decreasing subarray [peak+1..n] for the target in O(log n): use modified binary search that accounts for decreasing order (flip comparison directions).

Total cost: O(log n) to find the peak plus O(log n) for searches on each side. These add up to O(log n) overall, so the best possible asymptotic bound is Θ(log n).

Optimality note: this bound is tight because we provide an O(log n) algorithm and comparison-based searching among ordered sequences has an Ω(log n) decision-tree lower bound, so the asymptotic complexity is Θ(log n).