Visual walkthrough — Lower bound for comparison sorts — Ω(n log n) proof via decision trees

Step 0 — The one thing we assume: comparisons only

WHAT. We consider an algorithm that sorts $n$ distinct items but is only allowed one kind of move: pick two items, ask "is this one smaller than that one?", and get back yes or no. Nothing else. No looking at the actual numbers, no arithmetic on them.

WHY. This is the whole game. Everything that follows is squeezing out of this single restriction. If we let the algorithm peek at values (like Counting Sort does), the proof does not apply — and we'll see exactly why at the end.

PICTURE. Two cards face-down. You may only ask "left < right?".

Step 1 — Count the possible answers: there are $n!$ of them

WHAT. Before any question is asked, the items could be in any order. The number of distinct orderings of $n$ different items is $n!=\underset{\text{choices for 1st slot}}{\underbrace{n}}\times \underset{\text{then 2nd}}{\underbrace{(n-1)}}\times \cdots \times \underset{\text{2 slots left}}{\underbrace{2}}\times \underset{\text{last slot}}{\underbrace{1}}.$ Each factor is "how many items are still unplaced when I fill this slot".

WHY. The job of a sort is to name which of these orderings the input actually is (equivalently, which shuffle to undo). So the number of possible correct answers is exactly $n!$. That count is the mountain the algorithm must climb.

PICTURE. For $n=3$ there are $3!=6$ arrangements — all six shown as little card triples.

Step 2 — Draw the algorithm as a tree of questions

WHAT. Whatever the code does — loops, recursion, swaps — the only thing that steers it differently on different inputs is the answer to a comparison. So the entire behaviour is a binary tree:

• each internal node = one comparison "$a_i:a_j$",
• its two branches = the two answers (left for "yes / <", right for "no / ≥"),
• each leaf = the ordering the algorithm finally announces.

We call this the decision tree.

WHY. This is the key modelling trick: it turns "an algorithm" (hard to reason about) into "a tree" (easy to count). Running the algorithm on one input = walking one root-to-leaf path, taking the branch each answer dictates.

PICTURE. A small decision tree for $n=3$. Follow a path: two "yes"s send you left-left to a leaf.

Step 3 — Every ordering needs its own leaf

WHAT. Take any two different correct answers, say ordering $P$ and ordering $Q$. Their leaves must be different leaves.

WHY. A leaf outputs one fixed permutation. If $P$ and $Q$ landed on the same leaf, the algorithm would print the same permutation for both — but they need different answers, so it would be wrong for at least one input. Since all $n!$ orderings can occur and each needs a distinct reachable leaf: $\underset{\text{number of leaves}}{\underbrace{L}}\ge \underset{\text{distinct answers needed}}{\underbrace{n!}}$ Here $L$ just names "how many leaves the tree has".

PICTURE. Two inputs forced to different leaves; the "shared leaf" attempt is crossed out because it must give one input the wrong output.

Step 4 — A binary tree of height $h$ has at most $2^h$ leaves

WHAT. Count leaves top-down. At depth 0: 1 node. Each comparison has 2 answers, so each level can at most double the number of nodes. After $h$ levels: $L\le \underset{\text{doubling }h\text{ times from 1}}{\underbrace{2^h}}$ The exponent $h$ is the height; the base $2$ is "two answers per question".

WHY. This is the ceiling on how much you can distinguish with $h$ yes/no questions. Two answers per node is a hard fact — a comparison cannot return three things. So information capacity is capped at $2^h$.

PICTURE. Levels of a binary tree, each label showing $1,2,4,8,\dots ,2^h$ leaves — the doubling made visible.

Step 5 — Squeeze the two facts together

WHAT. Chain the two inequalities we earned: $2^h\ge L\ge n!⟹2^h\ge n!.$

• $2^h\ge L$ : capacity beats how many leaves you actually have (Step 4).
• $L\ge n!$ : you have at least $n!$ leaves (Step 3).
• The middle $L$ drops out, leaving capacity vs. demand: $2^h\ge n!$.

Now take ${\log }_2$ of both sides. ${\log }_2$ is the inverse of "2 to the power" — it asks "2 to what power gives this number?", which is precisely "how many yes/no questions does this many outcomes need?". That is why ${\log }_2$ and not $\ln$ or ${\log }_{10}$: our questions are binary. $h\ge {\log }_2(n!).$

WHY. ${\log }_2$ turns the towering $2^h$ into the plain $h$ we're hunting, and turns $n!$ into "the number of binary questions its size demands". The inequality survives the log because ${\log }_2$ is increasing (bigger input → bigger output), so it never flips the $\ge$.

PICTURE. The two curves $2^h$ (capacity) and the flat line $n!$ (demand): the tree only works once capacity rises above demand, and that crossing point is $h={\log }_{2}n!$.

Step 6 — Turn ${\log }_2(n!)$ into $\Omega (n\log n)$

WHAT. ${\log }_2(n!)$ is exact but ugly. We want a clean, easily-read lower bound. Trick: keep only the top half of the factors of $n!$ and throw the small ones away. To make "half" precise for every $n$ — even or odd — we use the floor $\lfloor n/2\rfloor$ (round down): it is the largest whole number $\le n/2$, so $\lfloor n/2\rfloor$ counts exactly how many factors sit in the top half. $n!=1\cdot 2\cdots \lfloor \frac{n}{2}\rfloor \cdots n\ge \underset{\ge \lceil n/2\rceil \text{ factors, each }\ge \lfloor n/2\rfloor }{\underbrace{\lfloor \frac{n}{2}\rfloor \cdot (\lfloor \frac{n}{2}\rfloor +1)\cdots n}}\ge \lfloor \frac{n}{2}{\rfloor }^{n/2}.$

• First ≥: dropping the factors $1,\dots ,\lfloor \frac{n}{2}\rfloor -1$ (all ≥ 1) can only shrink the product.
• Second ≥: the kept factors run from $\lfloor n/2\rfloor$ up to $n$ — at least $n/2$ of them, and every one is $\ge \lfloor n/2\rfloor$.

Take ${\log }_2$ (which turns a product-power into a multiplication): ${\log }_2(n!)\ge \underset{\text{how many factors}}{\underbrace{\frac{n}{2}}}\cdot \underset{\text{log of each factor}}{\underbrace{{\log }_2\lfloor \frac{n}{2}\rfloor }}=\Omega (n\log n).$

WHY. We only need a lower bound, so we're allowed to be wasteful and discard the small factors — that keeps the inequality honest while making it dead simple. The floor $\lfloor \cdot \rfloor$ is not cosmetic: for odd $n$ (say $n=7$) there is no whole factor equal to $n/2=3.5$, so we anchor on $\lfloor 7/2\rfloor =3$, which really is a factor and really bounds all the kept ones from below. Even $n$ just gives $\lfloor n/2\rfloor =n/2$ exactly — so the same formula covers both parities with no gap. The $\Omega$ notation (see Big-O and Asymptotic Notation) means "grows at least this fast, ignoring constants," which is all a lower bound claims.

PICTURE. The factor bars $1,2,\dots ,n$; the discarded left half greyed out, the kept right half each flattened down to the height $\lfloor n/2\rfloor$ — showing the "$\ge n/2$ copies of $\ge n/2$" bound.

Step 7 — The escape hatch: why Counting Sort isn't bound

WHAT. Counting sort runs in $O(n+k)$ (linear when the key range $k=O(n)$) — apparently beating $n\log n$. No contradiction.

WHY. It does count[x]++ — it indexes an array by the value $x$. That's not a comparison; it's peeking at the number itself. Our Step 0 assumption is broken, so the tree model never applied, so the bound never bound it. Same escape for Radix Sort.

PICTURE. Two doors: the "comparisons-only" door leads into the tree (bound applies); the "read the value" door bypasses the tree entirely.

The one-picture summary

Everything on one canvas: $n!$ orderings feed into a binary tree; each ordering claims a leaf; the tree of height $h$ holds at most $2^h$ leaves; so $2^h\ge n!$, hence $h\ge {\log }_{2}n!=\Omega (n\log n)$.

Active-recall