GATE 2025 CS2 Q.41: solution and answer

GATE 2025 · CS2Q.41 · 2 marks · MCQ

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)
$Θ (n)$
(B)
$Θ (1)$
(C)
$Θ (lo g^{2} n)$
(D)
$Θ (lo g n)$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The best possible worst-case bound is $Θ (lo g n)$ — option D.

Official answer: DSource: Official answer key, GATE 2025 CS2 (IIT Roorkee)

A bitonic array rises (non-decreasing) up to some peak index $i$ and then falls (non-increasing) after it; since all elements are distinct, both the rising part $A [1.. i]$ and the falling part $A [i + 1.. n]$ are strictly monotonic.
Stage 1 — locate the peak in $O (lo g n)$ comparisons: at a probe index $m$ , compare $A [m]$ with its neighbours. If $A [m - 1] < A [m] < A [m + 1]$ the peak lies to the right; if $A [m - 1] > A [m] > A [m + 1]$ it lies to the left; otherwise $A [m]$ itself is the peak. Each such probe (a constant number of comparisons) discards half the remaining range, exactly like binary search, so the peak index $i$ is found using $O (lo g n)$ comparisons.
Stage 2 — search each monotonic half: once $i$ is known, $A [1.. i]$ is sorted ascending and $A [i + 1.. n]$ is sorted descending. An ordinary binary search for the target on $A [1.. i]$ costs $O (lo g n)$ comparisons, and a binary search (with the inequality direction reversed) on $A [i + 1.. n]$ also costs $O (lo g n)$ comparisons. In the worst case the target can require probing both halves, but that only adds two $O (lo g n)$ terms.
Total worst-case cost: $O (lo g n)$ (find peak) $+ O (lo g n)$ (binary search the halves) $= O (lo g n)$ .
This bound is also the best possible one: searching for an arbitrary target among $n$ distinct candidate values, using only comparisons, is a decision problem with $n$ (or $n + 1$ , including "not found") possible outcomes, so any comparison-based search algorithm needs $Ω (lo g n)$ comparisons in the worst case, on any array — bitonic or otherwise. Combining the matching upper and lower bounds gives a worst-case comparison count of $Θ (lo g n)$ .
This rules out the other options: $Θ (n)$ is what a naive linear scan gives, far more than necessary; $Θ (1)$ is impossible because the target can be any one of $n$ values and the algorithm must in general inspect enough elements to distinguish among them; $Θ (lo g^{2} n)$ is achievable (e.g. binary searching both halves without first locating the peak) but is not the best possible bound, since the two-stage algorithm above already achieves the smaller $Θ (lo g n)$ . Hence the correct choice is option D.

KEY IDEA

A bitonic array can be searched in two binary-search-style stages — first locate the peak (the point where the array switches from ascending to descending), then binary-search whichever monotonic half is needed — giving $O (lo g n)$ comparisons; since any comparison-based search over $n$ distinct values needs $Ω (lo g n)$ comparisons in the worst case, the tight, best-possible bound is $Θ (lo g n)$ .

WATCH OUT FOR

Assuming a bitonic array needs $Θ (lo g^{2} n)$ comparisons because it "looks like" you must binary-search twice (once to find the peak, once inside a half) and multiplying the two $O (lo g n)$ stages together instead of adding them — the two stages are sequential (add), not nested (multiply), so the total stays $O (lo g n)$ , not $O (lo g^{2} n)$ .

From the GATE 2025 CS2 paper. Every question of this paper · Download the full paper · All 18 Sorting & hashing questions, with notes

GATE 2025 CS2 Q.41: solution and answer

Answer and solution

More Sorting & hashing questions