The GATE Grind

GATE 2025 CS (CS2) – Question 41

Algorithms · Searching, Sorting and Hashing · 2 marks · Multiple choice

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

  1. $\Theta(n)$
  2. $\Theta(1)$
  3. $\Theta(\log^2 n)$
  4. $\Theta(\log n)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $\Theta(\log n)$

Explanation

Binary search locates the peak in $O(\log n)$, then binary search on the increasing part and the decreasing part costs $O(\log n)$ each. The total is $\Theta(\log n)$, and $\Omega(\log n)$ holds as a lower bound.