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

Want the full step-by-step worked solution? It's part of Premium — along with a worked solution for every question in the bank.

Asked at: Citadel, DRW

Related questions