Question

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. $\Theta$ (1)
• B. $\Theta$ (n log n)
• C. $\Theta$ (n log n)
• D. $\Theta$ (n)

Answer 1

The correct option is A $\Theta$ (1)

Take first 3 elements. The middle of the 3 elements will be the element that is neither minimum nor maximum in the array. Hence O(1) time to compare 3 elements.
Example: Assume 4. 6, 2 are first three elements. Then 4 is the middle element of 4. 6 and 2. Which is neither minimum nor maximum.