GATE 2014 CS (CS1) – Question 49

Algorithms · Searching, Sorting and Hashing · 2 marks · Numerical answer

Find the minimum comparisons needed to find both minimum and maximum of 100 numbers.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 147.1 to 148.1

Explanation

Pair the100elements and compare within each pair, using50comparisons. Find the minimum among50pair-losers and maximum among50pair-winners, using49+49more. Total **148comparisons**, achieving the3n/2−2 lower bound for even n.