the decision-tree model

Picture an algorithm as a flowchart of yes/no questions. You start at the top, ask one question about the input, and depending on the answer you go left or right to the next question, and so on until you reach a leaf that announces the answer. A decision tree is exactly this picture: a tree whose internal nodes are comparisons and whose leaves are possible outputs. It is a way to DRAW any comparison-based algorithm so we can reason about it geometrically.

Here is how to read it for sorting. Each internal node holds a comparison like 'is A[i] < A[j]?'; the two children are the 'yes' and 'no' continuations. A particular input traces one path from root to leaf, and the leaf must name the correct sorted order (the permutation) for that input. Because the algorithm is deterministic, the same comparisons in the same order always send a given input to the same leaf. The number of comparisons that input costs in the worst case is the depth of the deepest leaf — the height of the tree. So 'worst-case comparisons of the best algorithm' becomes 'smallest possible height of a correct decision tree', a clean combinatorial quantity we can bound.

This re-drawing is the engine behind the most famous lower bounds. To be correct, the tree must have at least one leaf for every distinct output the algorithm might need to produce; a binary tree with L leaves has height at least log2(L); so the worst-case comparison count is at least log2(L). For sorting n items there are n! possible orderings, forcing L >= n! and height >= log2(n!) = Omega(n log n). The model is honest about its scope: it captures only algorithms whose sole way of learning about the input is comparisons, and the 'cost' it measures is comparison count, ignoring bookkeeping like moving elements — which is fine, since those bookkeeping steps cannot be cheaper than the comparisons that drive them.