Exact comparisons for min and max

You must find both the minimum and the maximum of n=100n = 100 distinct numbers using the fewest element comparisons. Work out the exact minimum number of comparisons that always suffices (not the ∼3n2\sim\tfrac{3n}{2} ballpark - the precise integer).

Show hints (2)+
  1. Pair the numbers first: 5050 pair-offs split them into max-candidates and min-candidates.
  2. Then 4949 to reduce each group; total 50+49+4950+49+49. Derive the −2-2, don't just quote 3n/23n/2.

Answer

Reveal answer →

148

Create a free account to see the full worked solution and track your progress.

Interview format: Hedge Fund Quant, Prop Trading

Related questions