An unordered list contains \(n\) distinct elements. The number of comparisons…
2015
An unordered list contains \(n\) distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is
- A.
\(Ɵ(n \ log \ n)\) - B.
\(Ɵ(n)\) - C.
\(Ɵ(log \ n)\) - D.
\(Ɵ(1)\)
Attempted by 398 students.
Show answer & explanation
Correct answer: D
Key idea: you only need to examine a constant number of elements (three) to find an element that is neither the maximum nor the minimum.
Take any three distinct elements from the list.
Find the median (middle) of these three. This takes at most 3 comparisons in the worst case.
The median among the three cannot be the global maximum (because one of the other two is larger) and cannot be the global minimum (because one of the other two is smaller).
Conclusion: You can always produce an element that is neither the maximum nor the minimum using at most 3 comparisons, so the number of comparisons is Θ(1).
A video solution is available for this question — log in and enroll to watch it.