Question

Consider an unordered list of \(N\) distinct integers. What is the minimum number of element comparisons required to find an integer in the list that is NOT the largest in the list?

• A. \(1\)
• B. \(N-1\)
• C. \(N\)
• D. \(2N-1\)

Hint:

When searching for a non-maximum element in an unordered list, a single comparison is sufficient as soon as we find any element smaller than the maximum.

Answer 1

The Correct Option is A

To determine a number that is not the largest in an unordered list of \(N\) distinct integers, we only need to compare two elements.

• If we compare any two distinct elements, at least one of them is guaranteed to be smaller than the maximum.
• This means that in just one comparison, we can confirm that one of the numbers is not the largest.

Since we only need to confirm that one of the two numbers is smaller than the maximum, the minimum number of comparisons required is 1.