Project ForgeAlgorithms
Sorting & Searching
GATE 2007
Hard
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?
- AAt least 2n - c comparisons, for some constant c, are needed
- At most 1.5n - 2 comparisons are needed
- CAt least n log₂ n comparisons are needed
- DNone of the above
Explanation
The classic pairwise-comparison technique (compare elements in pairs, then compare each pair's winner against the running max and loser against the running min) finds both max and min using exactly ⌈3n/2⌉-2 comparisons, which for even n equals 1.5n-2 — a tight optimal bound, well below both 2n-c and n log₂ n.
Source: GATE CS 2007 (2007)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.