An array of n numbers is given, where n is an even number. The maximum as well…
2007
An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?
- A.
At least 2n - c comparisons, for some constant c, are needed.
- B.
At most 1.5n - 2 comparisons are needed.
- C.
At least nLog2n comparisons are needed.
- D.
None of the above.
Attempted by 106 students.
Show answer & explanation
Correct answer: B
Key idea: reduce the number of candidates for min and max by comparing elements in pairs.
Step 1: Pair up the n elements (n is even) and compare the two elements in each pair. This uses n/2 comparisons and yields one local minimum and one local maximum per pair.
Step 2: Find the global maximum by comparing the n/2 local maxima. This requires (n/2) - 1 comparisons.
Step 3: Find the global minimum by comparing the n/2 local minima. This also requires (n/2) - 1 comparisons.
Total comparisons: n/2 + (n/2 - 1) + (n/2 - 1) = 3n/2 - 2 = 1.5n - 2.
Conclusion: the statement that at most 1.5n - 2 comparisons are needed is true. The described algorithm achieves this bound, which is worst-case optimal up to rounding (the exact worst-case lower bound is ceil(3n/2) - 2).
A video solution is available for this question — log in and enroll to watch it.