The Decision-Tree Model

Why we need a model at all

The previous guide drew a sharp line: a lower bound is a claim about the problem, not about one program. It says every correct algorithm must pay at least so much. But that word 'every' is a trap. There are infinitely many algorithms — clever ones, ugly ones, ones nobody has invented yet. How could you possibly reason about all of them at once? You cannot, unless you first pin down precisely what counts as 'an algorithm' for the task. That pinned-down description is called a computational model, and choosing one is the first honest step of any lower-bound proof.

For sorting and searching, the natural model is the comparison model. In it, an algorithm is allowed to learn about its input only by comparing two elements and asking 'is a less than b?' It may compare, branch on the answer, move data around, and remember whatever it likes — but the only window onto the actual values is the yes/no result of comparisons. Merge sort, quicksort, heapsort, insertion sort, binary search: all of them live inside the comparison model. They never peek at the bits of a number except through a comparison.

Drawing an algorithm as a tree

Here is the beautiful move. Once an algorithm may only ask comparison questions, its entire behaviour collapses into a tree of questions. Each internal node is one comparison — 'a_i < a_j?' — with two children, one for 'yes' and one for 'no'. The algorithm starts at the root, asks the comparison there, walks left or right depending on the answer, asks the next question at the node it lands on, and so on. It performs no other kind of step that affects the path. When it finally stops, it has reached a leaf, and the leaf carries the answer the algorithm outputs. This picture is the decision-tree model.

Two facts about this tree are the engine of everything that follows. First, running the algorithm on a particular input traces exactly one root-to-leaf path, and the number of comparisons it makes on that input is the length of that path. So the worst-case number of comparisons is the height of the tree — the longest root-to-leaf path. Second, the tree is fixed once the algorithm and the input size n are fixed. Different inputs of the same size send you down different paths, but they all wander the same tree. The algorithm is the tree.

       a1 < a2 ?
        /       \
      yes        no
      /            \
   a2 < a3 ?     a1 < a3 ?
    /    \         /    \
 [1,2,3] ...    ...   [3,2,1]
  (a leaf =      (each leaf is one
   one output)    possible answer)

Counting leaves: the information argument

Now comes the leap that turns a drawing into a theorem. Look at the leaves from the problem's side, not the algorithm's. A correct algorithm must be able to produce every answer the problem might require. So the tree must have at least one leaf for every distinct correct answer. If two genuinely different inputs demand two different outputs, they must end at two different leaves — otherwise the algorithm would give the same answer to both, and be wrong on at least one. This is the heart of the information-theoretic lower bound: enough leaves to tell every case apart.

And a binary tree cannot hide many leaves under a short height. Each comparison has only two outcomes, so a tree of height h has at most 2^h leaves — every extra level can at most double the leaf count. Turn that around: if the tree needs at least L leaves, its height must satisfy 2^h >= L, which means h >= log2(L). Since height is the worst-case comparison count, any comparison algorithm for a problem with L distinct answers needs at least log2(L) comparisons in the worst case. The whole argument is two short steps: count the answers you must distinguish, then take a log.

1. Fix the comparison model and the input size n, so the algorithm is a fixed binary decision tree.
2. Count L = the number of distinct correct answers the problem can demand at size n.
3. Argue the tree needs at least L leaves: different required answers force different leaves.
4. A binary tree of height h has at most 2^h leaves, so 2^h >= L, hence height h >= log2(L).
5. Height is the worst-case comparison count, so log2(L) comparisons are unavoidable.

A first taste: it explains binary search

Let us run the machine on something we already trust, to feel that it gives the right answer. Take searching a sorted array of n elements: report which position the target matches, or that it is absent. The distinct answers are 'position 1', 'position 2', ..., 'position n', plus 'not found' — call it n+1 outcomes. The recipe says any comparison search needs at least log2(n+1) comparisons in the worst case. That is exactly the Theta(log n) cost of binary search, and now we know it is not just a good method — no comparison method can do asymptotically better. The sorted-search lower bound is the decision tree at its gentlest.

Notice what the bound does and does not claim — the same honesty the first guide insisted on. log2(n+1) is a worst-case count of comparisons, in this one model. It says nothing about constant factors of real wall-clock time, nothing about cache behaviour, and nothing about models that read keys directly. It is a statement about the structure of information: to single out one of n+1 possibilities using yes/no questions, you must ask about log2(n+1) of them. That is why this style of bound is called information-theoretic — it counts how many bits of answer you are obliged to extract.

What the model can and cannot reach

The next guide cashes this in for the headline result: sorting n elements has n! possible orderings as answers, so the tree needs n! leaves, and log2(n!) works out to Theta(n log n). That single calculation is the famous comparison-sorting barrier — and the decision tree is the entire reason it holds. But it is worth being clear-eyed about the model's reach before we get there. The argument is exact within the comparison model and silent outside it: it never bounds counting sort, never bounds an algorithm that hashes, never bounds anything that touches values except through comparisons.

The decision tree is also not the only lower-bound tool, and it has blind spots. It counts comparisons cleanly but says little about subtler problems where you want to show a particular hard input — for those, the adversary argument of guide 4 is sharper, imagining an opponent who answers each comparison to keep the algorithm in the dark as long as possible. And when one problem's hardness is best shown by leaning on another's, the reduction of guide 5 carries the bound across. The decision tree is the foundation these later tools build on, not the last word.

One last honest caveat about reading these bounds at human scales. A worst-case comparison count is an asymptotic, structural statement; it is not a verdict at every n. log2(n) comparisons may each be slow if elements are huge, and an O(n^2) method with tiny constants can still beat a log-optimal one for small inputs — the same caution about Big-O hiding constants that the asymptotics rung hammered. The decision tree tells you the true shape of the cost. It does not promise the fastest stopwatch on your laptop today.