Project ForgeAlgorithms
Complexity Analysis
GATE 2014
Medium
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is __________.
148(± 1 accepted)
Explanation
The optimal tournament-style method processes elements in pairs: for each pair, 1 comparison determines the local min and max, then each new candidate min/max only needs to be compared against the running min/max (not against both), giving ⌈3n/2⌉−2 comparisons overall. For n=100 (even): 3(100)/2 − 2 = 150 − 2 = 148.
Source: GATE CS 2014 (Session 1) (2014)
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.