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

WHAT are we even claiming?

WHY does this matter? It tells you merge sort / heapsort ($O(n\log n)$) are asymptotically optimal — no clever comparison-only algorithm can ever beat them. It also explains WHY counting sort / radix sort ($O(n)$) must cheat: they use the values themselves (indexing into buckets), not just comparisons.

HOW: the decision tree model

The derivation — from scratch

We want a lower bound on the height $h$ of the decision tree.

Step 1 — Every permutation needs its own leaf. There are $n!$ distinct orderings of $n$ distinct elements. The algorithm must output the correct one for each input. If two different required permutations shared the same leaf, the algorithm would output the same answer for both — wrong for at least one.

Why this step? The leaf is the final answer; one answer per leaf, and we need every correct answer reachable. So: $\text{(number of leaves)} \;\ge\; n!$

Step 2 — A binary tree of height $h$ has at most $2^h$ leaves. At depth 0 there's 1 node; each level at most doubles. A tree of height $h$ has at most $2^h$ leaves.

Why this step? Each comparison has only 2 outcomes, so the tree is binary, and $h$ comparisons ⇒ at most $2^h$ distinct root-to-leaf paths.

Step 3 — Combine. $2^h \;\ge\; (\text{leaves}) \;\ge\; n! \quad\Longrightarrow\quad h \;\ge\; \log_2(n!)$

Step 4 — Bound $\log_2(n!)$ from below. We need $\log_2(n!) = \Omega(n\log n)$. Use the lower half of the factorial: $n! = 1\cdot 2 \cdots n \;\ge\; \underbrace{\frac{n}{2}\cdot\left(\frac{n}{2}+1\right)\cdots n}_{n/2 \text{ terms, each} \ge n/2} \;\ge\; \left(\frac{n}{2}\right)^{n/2}$

Why this step? Throwing away the small factors ($1,2,\dots,\tfrac n2-1$) only makes the product smaller, and every remaining factor is $\ge n/2$ — a clean, easy bound. Taking $\log_2$: $\log_2(n!) \;\ge\; \frac{n}{2}\log_2\!\frac{n}{2} \;=\; \frac{n}{2}(\log_2 n - 1) \;=\; \Omega(n\log n).$

Worked examples

Common mistakes (steel-manned)

Active-recall flashcards

Connections

• Merge Sort — achieves the $O(n\log n)$ upper bound, proving optimality.
• Heapsort — another $\Theta(n\log n)$ comparison sort meeting the bound.
• Quicksort — average $O(n\log n)$; worst case $O(n^2)$ but still bounded below by $\Omega(n\log n)$ on average.
• Counting Sort / Radix Sort — non-comparison sorts that legally beat $n\log n$.
• Big-O and Asymptotic Notation — meaning of $\Omega$.
• Information Theory & Entropy — $\log_2(n!)$ bits of information must be extracted.
• Binary Search — same "$\log$ of outcomes" counting idea, for $n$ outcomes.
• Stirling's Approximation — used to sharpen $\log_2(n!)$.

Concept Map

Hinglish (regional understanding)