The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is ________
GATE 2014 · Algorithms · Sorting · medium
Answer: 148 comparisons (using the pair-wise tournament algorithm: 3*floor(n/2) - 2 for even n=100)
- Naive approach (for comparison): Find minimum: n-1 comparisons. Find maximum separately: n-1 comparisons. Total = 2(n-1) = 2*99 = 198 comparisons.
- Tournament (pair-wise) algorithm: Step 1: Compare first two elements a[0] and a[1] (1 comparison). Set min = smaller, max = larger. For i = 2, 4, 6, ..., 98 (49 pairs): Compare a[i] with a[i+1] (1 comparison) Compare smaller of pair with current min (1 comparison) Compare larger of pair with current max (1 comparison) Total comparisons = 1 + 49*3 = 1 + 147 = 148. Formula check: 3*(100/2) - 2 = 150 - 2 = 148.