GATE CS 2015 Set 2 Q22 — Asymptotic Worst Case Time and Space Complexity

To find an element in an unordered list of $n$ distinct elements ($n \ge 3$) that is neither the maximum nor the minimum, we can use a constant-time approach:

1. Pick any three arbitrary elements from the list, for example, the first three elements: $a$, $b$, and $c$.
2. Find the median of these three elements.

Why does this work?

• Let the median of the three elements be $m$. By definition of a median of three distinct elements, one element is strictly smaller than $m$ and one element is strictly larger than $m$.
• Since there is at least one element in the list smaller than $m$, $m$ cannot be the global minimum.
• Since there is at least one element in the list larger than $m$, $m$ cannot be the global maximum.

Comparison Complexity:

Finding the median of three elements requires at most $3$ comparisons. Since this number of comparisons is independent of $n$, the time complexity is $\Theta(1)$.

Therefore, the correct option is D.