An unordered list contains n distinct elements. The number of comparisons to…

Concept: An algorithm runs in Θ(1) — constant time, independent of n — whenever the work it performs is bounded by a fixed number of steps that never grows as the input size n increases. To show that some element of an n-element set is neither the overall maximum nor the overall minimum, it suffices to exhibit one other element larger than it and one other element smaller than it — and both of those can come from a small, fixed-size sample rather than the whole set.

Application:

1. Pick any three distinct elements a, b, c from the n-element list.

2. Compare a, b, and c pairwise (at most 3 comparisons) to identify their median — the value that is neither the largest nor the smallest of the three.

3. Because one of the other two picked elements is larger than this median and one is smaller, the median cannot equal the overall maximum of the whole list (something bigger exists) and cannot equal the overall minimum (something smaller exists).

4. So this median value is guaranteed to be an element of the list that is neither the global maximum nor the global minimum.

Cross-check: For the smallest valid case, n = 3, the three picked elements ARE the entire list, and the argument still holds — the median is neither the list's maximum nor its minimum. For any larger n, additional elements exist elsewhere in the list, but the procedure never needs to inspect them: it always examines exactly 3 elements, regardless of how large n is.

Since the number of comparisons is bounded by a constant (at most 3) and does not grow with n, the time complexity is Θ(1).