GATE CS 2025 Set 2 Q.41: Searching and Sorting Algorithms

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$ ?

$\Theta(n)$

$\Theta(1)$

$\Theta(\log^2 n)$

$\Theta(\log n)$

Official answer and solution

Official answer: D
From: Official GATE 2025 answer key

Solution

Find the bitonic peak index $i$ in $O(\log n)$ comparisons via binary search, then binary-search both monotonic halves in $O(\log n)$ comparisons.

Upper bound $O(\log n)$ : Using binary search on adjacent elements ( $A[m]$ vs. $A[m+1]$ ), we can locate the peak index $i$ of the bitonic array in $O(\log n)$ comparisons. Once $i$ is known, $A[1..i]$ is strictly increasing and $A[i+1..n]$ is strictly decreasing, so two standard binary searches take $O(\log n)$ comparisons.
Lower bound $\Omega(\log n)$ : Any sorted array is a special case of a bitonic array (with $i = n$ ), and searching a sorted array of $n$ distinct elements requires $\Omega(\log n)$ comparisons in the worst case.

Thus the best possible worst-case bound is $\Theta(\log n)$ .

Final answer

Option (D)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 2 (CS2)
Question: 41 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source