Why does finding the maximum of n tournament seeds require at least n-1 comparisons?
answer
- count what one comparison can rule out
- how many seeds must be ruled out?
- a comparison produces at most one loser
- n-1 non-winners each need eliminating
- unbeaten seed could be the largest
basics
~20 sEvery seed except the winner must lose a comparison before it can be ruled out, and one comparison rules out at most one seed. With n-1 to eliminate, no correct algorithm uses fewer than n-1 comparisons.
solid answer
~40 sThink of it as eliminations in a bracket. For the answer to be correct, every seed other than the reported winner needs evidence against it — some comparison in which it was not the larger side. One comparison produces at most one such loser, so eliminating n-1 non-winners costs at least n-1 comparisons. The adversary phrasing is sharper: if an algorithm stops after fewer than n-1 comparisons, some seed never lost anything, and an adversary can consistently make that seed the largest — so the algorithm answers wrongly on one of two inputs it cannot tell apart. This is a bound on the **problem**, and the naive single scan matches it exactly, which makes the trivial algorithm provably optimal. No structure, index or preprocessing beats it for a one-shot query.
code
pseudocode · 8 lines// bracket[0..n-1] holds seed ratings for one round
best = bracket[0]
for i in 1..n-1
if bracket[i] > best
best = bracket[i]
// whichever value lost this comparison is now eliminated
return best
// comparisons performed: n-1, matching the proven floorgo deeper
Recall that scanning once while keeping the best value so far finds the maximum using exactly n-1 comparisons, and that no shortcut beats a single pass over raw data.
Be able to give the elimination argument out loud: each comparison rules out at most one candidate, and n-1 candidates must be ruled out. That is what makes the naive scan provably optimal rather than merely adequate.
Demonstrate that you check whether the query is one-shot or repeated. Maintained structures make the query cheap by paying at update time, so ask where the work moved before accepting that a floor was beaten.
Judge when proving a small bound is worth the meeting. Its value is stopping a team from optimising something already optimal and redirecting that effort to where the real cost actually sits.
## The claim Given n seed ratings entering a tournament round, any correct algorithm that determines the largest one must perform at least n-1 comparisons in the worst case. And a single left-to-right scan holding the best value so far performs exactly n-1. Upper bound meets lower bound: the naive algorithm is **optimal**, and there is no cleverness to buy. This is worth internalising precisely because the instinct in interviews is that the obvious algorithm is the placeholder for something better. Sometimes there is nothing better, and being able to prove it is a distinguishing skill. ## The elimination argument Call a seed *eliminated* once some comparison has shown it is not the largest — that is, once it has been on the losing side of at least one comparison. When the algorithm reports a winner, every one of the other n-1 seeds must be eliminated; otherwise there is a seed the algorithm never saw lose, and it has no grounds to exclude it. Now count what a comparison can accomplish. Comparing two seeds returns one of *greater*, *less*, or *equal*. In each case, at most one of the two can be dropped from contention. So each comparison contributes at most one elimination, and n-1 eliminations require at least n-1 comparisons. The tie case is worth stating explicitly, because it is where the argument is often assumed to break: if two seeds compare equal, you may discard one of them from the search for a maximum *value*, but not both. At most one elimination, exactly as before. Duplicates do not buy the algorithm anything. ## The adversary phrasing The same fact stated as a game: an adversary chooses the numbers *after* watching what the algorithm does. Suppose the algorithm halts after fewer than n-1 comparisons. Then some seed s was never on the losing side of any comparison. The adversary now assigns values consistent with every answer already given, but making s the largest. The algorithm's execution is identical — it saw the same comparison outcomes — yet the correct answer differs. So it must be wrong on at least one of those inputs. Adversary arguments are the general tool for lower bounds. You do not enumerate algorithms; you show that whatever the algorithm does, the input can be filled in to defeat it. ## What the bound counts, and what it does not It counts **comparisons**, in the worst case, over all algorithms in the comparison model. It is not a claim about wall-clock time, memory traffic or cache behaviour, and it is not a claim about a single input — an algorithm that guesses right early still has to check. It also assumes a one-shot query over raw data. If the seeds are maintained in a structure kept ordered under updates, answering "who is the maximum" becomes constant-time, but the work has moved to insertion time rather than vanished. Whenever someone reports beating a floor like this, the first question is whether the cost was removed or relocated — it is almost always relocated. ## Floors are problem-specific A useful contrast: finding the maximum **and** the minimum together. The obvious approach compares every element against both running extremes, costing roughly 2n comparisons. Pairing does better — compare elements two at a time, then send the larger of the pair against the running maximum and the smaller against the running minimum. That costs about 3n/2 comparisons, and 3n/2 is also the proven floor for that problem. So the honest statement is not "extremes cost 2n" but "each problem has its own floor, and you find it by counting what each comparison can accomplish." The same counting technique extends further: the second-largest element can be found in n plus about log n comparisons using a knockout bracket, because the true second-largest must be one of the seeds that lost directly to the winner, and that is a small set. All of these results come from the same move — count what evidence the answer requires, then count what one comparison can supply. ## Interview register The wrong answer this hunts for is "you could do better with a smarter data structure" or "sort first, then take the last element." Sorting is strictly worse: it establishes far more information than the question asked for, at a higher floor. The right answer names the resource being counted, states what a single unit of it can achieve, and divides.
- If you build a heap over the seeds first, does that beat the n-1 floor for a single maximum query?No. Bottom-up heap construction is O(n) but performs roughly 2n comparisons — more than the scan, not fewer. It cannot beat a proven floor; it only pays off when you need repeated extractions, where the ordering work is amortised across many queries. For one maximum, the plain scan is both optimal and simpler.
- The seeds arrive already grouped by division, each division tracking its own current best. Does the n-1 floor still apply?For a fresh maximum over raw seeds, yes — the floor is unchanged. What the grouping buys is a smaller query: comparing the divisions' precomputed bests costs one comparison per division. But those per-division maxima were maintained at update time, so the same total work was paid earlier. The floor was not beaten; the cost was moved off the query path.
A knockout bracket needs one match per elimination, and n-1 seeds have to be eliminated before exactly one remains standing.
saying these in an interview costs you the question
- Claims a smarter structure finds a maximum sublinearly
- Says you must sort first to find the maximum
- Treats the comparison count as a wall-clock time bound
- Assumes duplicate values weaken the elimination argument
- Thinks preprocessing raw unordered data is free