the leaf-counting argument for decision trees

Here is the small, reusable lemma that powers nearly every comparison lower bound, stated once so you can apply it everywhere. A binary tree where every internal node has at most two children and there are L leaves cannot be short: its height must be at least log2(L). Intuitively, each level can at most double the number of leaves, so to reach L leaves you need at least log2(L) levels. This is the engine; sorting and searching bounds are just this lemma fed different leaf counts.

The full argument has three clean steps that you reuse verbatim. Step one, MODEL: draw the comparison algorithm as a binary decision tree, internal nodes are comparisons, leaves are outputs, and the worst-case number of comparisons equals the tree's height. Step two, COUNT LEAVES: argue that correctness forces at least L leaves, because the algorithm must be able to output every distinct answer it might need, and distinct answers require distinct leaves (two different correct outputs cannot share a leaf, since a leaf commits to one output). Step three, HEIGHT FROM LEAVES: apply the lemma height >= log2(L). Plug in L = n! for sorting to get Omega(n log n); plug in L = n+1 for sorted search to get Omega(log n). The same three steps, different L.

Two honest points about scope and tightness. The lemma needs a BINARY branching factor: each comparison must have at most two relevant outcomes. If a node can branch three ways (a <, =, > comparison genuinely using all three), replace log2 by log3, which changes the constant but never the Omega — three-way branching can save at most a constant factor. And the argument is tight only when an algorithm actually achieves a balanced tree of height about log2(L); a correct lower bound proves you cannot do better, but matching it requires a real algorithm (merge sort, binary search) that reaches the floor. The leaf-counting argument gives the floor; the algorithm shows the floor is reachable, and together they pin the complexity to Theta.