-
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?
-
- At least 2n – c comparisons, for some constant c, are needed
- At most 1.5n – 2 comparisons are needed
- At least nlog2 n comparisons are needed
- None of the above
- At least 2n – c comparisons, for some constant c, are needed
Correct Option: B
One possible way to do this is we select first element as max & also min. Then we compare it with all others. At most this would take 2n comparisons during linear search. But if we use divide & conquer as for merge sort we have.
T(n) 2T(n / 2) + 2 for n > 2
T(n) = 3n / 2 – 2
= 1.5n - 2
