How do you derive the comparison-sort lower bound from a decision tree?
answer
- model every possible run as a branching tree
- count the outcomes you must tell apart
- n! orderings need n! reachable leaves
- height h binary tree: at most 2^h leaves
- Stirling turns log2(n!) into n log n
basics
~20 sModel the sort as a binary tree of comparisons whose leaves are output orderings. Correctness forces n! leaves, a height-h binary tree holds at most 2^h, so h >= log2(n!), which Stirling puts at Theta(n log n).
solid answer
~50 sFix an algorithm and a size n, and trace every possible run. Each comparison has two outcomes, so the runs form a binary tree: internal nodes are comparisons, edges are answers, and a leaf is where the algorithm stops and emits a permutation. Correctness forces distinct leaves for distinct input orderings — two orderings reaching the same leaf get the same rearrangement applied, and at most one result can be sorted — so the tree needs at least `n!` reachable leaves. A binary tree of height `h` has at most `2^h` leaves, hence `2^h >= n!` and `h >= log2(n!)`. Stirling's approximation gives `log2(n!) = n log2 n - n log2 e + O(log n)`, so the worst-case path is `Omega(n log n)`. The height is the worst-case comparison count, which is what we wanted to bound.
code
pseudocode · 8 linesif a[0] < a[1]:
if a[1] < a[2]: emit order (0, 1, 2)
else if a[0] < a[2]: emit order (0, 2, 1)
else: emit order (2, 0, 1)
else:
if a[0] < a[2]: emit order (1, 0, 2)
else if a[1] < a[2]: emit order (1, 2, 0)
else: emit order (2, 1, 0)go deeper
Learn the shape of the argument before the algebra: possible runs form a tree, correctness needs one leaf per ordering, and a short tree cannot have enough leaves. Being able to say that much already puts you ahead.
Expect to derive it at a whiteboard: justify the n! leaves from correctness, state that a height-h binary tree has at most 2^h leaves, and finish with Stirling. Practise the n = 5 arithmetic so you can make it concrete on demand.
Show that you know what the proof buys: it constrains every algorithm in the model at once, including unwritten ones, which is why no engineering effort inside the comparison model can change the asymptotics of a sorting hot path.
Be ready to explain to a team why a proved lower bound closes a line of investigation. The strategic move is not to optimise harder but to decide whether the data justifies leaving the model, and to weigh that against the maintenance cost of a bespoke sort.
## Turning an algorithm into a tree The proof works because a comparison sort, viewed from far enough away, is nothing but a branching interrogation. Fix any correct comparison sort and fix the input size n. The algorithm's behaviour is determined entirely by the answers it receives, so you can draw the set of all possible executions as a tree: every internal node is labelled with the comparison the algorithm makes at that point, its two outgoing edges are the two possible answers, and every leaf is a place where the algorithm halts having decided on a final arrangement. This is called the **decision tree** for that algorithm at that input size. There is a different tree for every n, which is fine — the bound is asymptotic in n. Two properties of this tree matter, and both need justifying rather than asserting. **The tree is binary.** Each comparison of two distinct keys yields one of two answers. (Handling ties adds a third outcome; see the constant-factor discussion below — it does not change the conclusion.) **The tree needs at least n! reachable leaves.** Suppose two different input orderings of the same n distinct values follow the same root-to-leaf path. Then every comparison along the way gave the same answer for both, so the algorithm did exactly the same thing to both, and applied the same permutation to both. But the two inputs need *different* permutations to become sorted, so at least one of the two outputs is wrong. A correct algorithm therefore sends each of the n! orderings to its own leaf. Note the direction of the argument: it is not that the algorithm chooses to have n! leaves, it is that correctness leaves it no choice. ## From leaf count to height A binary tree of height h — h being the number of edges on its longest root-to-leaf path — has at most 2^h leaves, by induction on h. Combining: ``` 2^h >= (number of leaves) >= n! h >= log2(n!) ``` And the height of the decision tree *is* the worst-case number of comparisons the algorithm performs, because the longest path is a real execution, produced by some real input. So every correct comparison sort makes at least log2(n!) comparisons on some input of size n. ## Making log2(n!) legible Stirling's approximation gives `log2(n!) = n log2 n - n log2 e + O(log n)`, so log2(n!) is `Theta(n log n)`, and the leading term is exactly `n log2 n`. If you cannot recall Stirling in an interview, there is a two-line argument that gets the same class: `log2(n!) = log2 1 + log2 2 + ... + log2 n`; drop the smaller half of the terms and each of the remaining n/2 terms is at least log2(n/2), giving `log2(n!) >= (n/2) log2(n/2) = Omega(n log n)`. Beware of the mirror mistake: bounding every term by log2 n gives `log2(n!) <= n log2 n`, which is an *upper* bound and proves nothing here. ## The arithmetic that makes it concrete For n = 5 there are 5! = 120 orderings. log2(120) is about 6.907, and a comparison count must be a whole number, so **every comparison sort needs at least 7 comparisons to sort 5 elements in the worst case.** A tree of height 6 has at most 64 leaves and simply cannot separate 120 cases. Doing this arithmetic out loud is the fastest way to show an interviewer you understand the argument rather than reciting it — and it also exposes what the bound is *not*: seven is a floor, and the fact that a known merge-insertion scheme actually achieves seven for n = 5 is a separate, harder result. In general the floor is not always achievable. For n = 12 the counting bound gives 29 comparisons, but 30 are provably necessary; the information-theoretic argument does not know about the combinatorial awkwardness of particular sizes. ## What the proof does not use Read the argument again and notice the absences. No recursion, no pivots, no memory model, no assumption that the algorithm is efficient or even sensible. It applies to every comparison sort simultaneously — including the ones nobody has written yet, which is exactly why a lower bound is worth proving. Contrast this with an upper bound, which you establish by exhibiting one algorithm and analysing it. That asymmetry is the thing to say when an interviewer asks why anyone bothers proving lower bounds at all. ## Two refinements worth knowing First, the same tree gives an **average-case** bound: the average leaf depth of a binary tree with L leaves is at least log2 L, so a comparison sort averages Omega(n log n) comparisons over uniformly random input, not merely on one adversarial input. Randomizing the algorithm does not escape this either; it only moves the randomness from the input to the coin flips. Second, the proof assumes the keys are distinct. With duplicates there are fewer distinguishable outcomes — if the multiset has repeated values, several "orderings" are indistinguishable and the leaf count drops — which is precisely why sorts specialised for low-cardinality data can legitimately beat n log n comparisons on such inputs without contradicting anything.
- Why must two different input orderings end at two different leaves?Because a leaf fixes one rearrangement. If two orderings followed identical answers all the way down, the algorithm would apply the identical permutation to both, and two different starting orders cannot both become sorted under the same permutation. So at least one output would be wrong, which a correct algorithm does not permit.
- Work out the minimum comparisons to sort five elements in the worst case.There are 5! = 120 orderings, and a binary decision tree of height h separates at most 2^h of them. 2^6 = 64 is too few and 2^7 = 128 suffices, so the height is at least 7: no comparison sort orders five elements using six comparisons in the worst case. Equivalently, ceiling of log2(120) = ceiling of 6.907 = 7.
- Does the argument also bound the average number of comparisons?Yes. The average root-to-leaf depth of a binary tree with L leaves is at least log2 L, so a correct comparison sort averages at least log2(n!) comparisons over uniformly random inputs. That closes the obvious loophole: you cannot make the hard cases rare, because there are simply too many outcomes to encode with short paths.
- Is log2(n!) always achievable?No — it is a floor, not a recipe. For small sizes it is often attained, but not always: for twelve elements the counting bound is 29 comparisons while 30 are provably necessary. The information-theoretic argument only says how much information you need; it does not promise a strategy that extracts a full bit from every single comparison.
You are handed a shuffled deck and a balance scale that only says "left is lighter" or "right is lighter". With n cards there are n! possible arrangements and each weighing splits your remaining candidates in two at best, so no strategy can identify the arrangement in fewer than log2(n!) weighings.
saying these in an interview costs you the question
- Derives n log n from merge sort's recurrence instead of the model
- Says nobody has found a faster sort, so none exists
- Cannot explain why the tree must have n! leaves
- Confuses tree height with number of nodes or leaves
- Bounds each term by log2 n and calls it a lower bound
- Thinks the proof depends on the algorithm being recursive