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

Definition Quick symbol reminder (everything used on this page)

$n!$ (" $n$ factorial") $= 1 \cdot 2 \cdot 3 \dots n$ — the number of ways to arrange $n$ distinct things.
$lo g_{2} x$ answers "2 to the what power gives $x$ ?" — exactly the number of yes/no questions needed to pin down one of $x$ equally-likely possibilities.
Decision tree: a binary tree where each internal node is a comparison and each leaf is an output ordering. Running the algorithm = walking one path from the top (root) down to a leaf.
Height $h$ of the tree = the length of the longest root-to-leaf path, i.e. the maximum number of comparisons on any single input. This is the worst case. (A path of length $h$ has $h$ comparison-nodes on it.) Because each comparison node splits into 2 children, a tree of height $h$ has at most $2^{h}$ leaves.
$O (f)$ ("big-O of $f$ ") means "grows no faster than a constant times $f$ " — an upper bound. $Ω (f)$ means "grows at least as fast as a constant times $f$ " — a lower bound. $Θ (f)$ means "both at once" — grows exactly like $f$ up to constant factors. (Constant factors, like using $lo g_{2}$ vs $lo g_{3}$ , are ignored by all three.)

Level 1 — Recognition

(Can you spot what the model says and where it applies?)

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

Recall Solution 1.1

A comparison sort decides order using only questions of the form "is $a_{i} < a_{j}$ ?" — never reading the numeric value of a key.

(a) Bubble sort — yes. It swaps adjacent items based on a comparison.
(b) Counting sort — no. It does count[x]++, using the value $x$ as an array index.
(c) Heapsort — yes. Sift-up/sift-down compare children to parents.
(d) Radix sort — no. It buckets by digit value, not by comparison.
(e) Quicksort — yes. Partitioning compares each element to a pivot.

Rule of thumb: if it ever looks at a value (to index, hash, or arithmetic), it escapes the model. See Counting Sort and Radix Sort for the escapees, Merge Sort · Heapsort · Quicksort for the comparison crowd.

Recall Solution 1.2

(a) An internal node is a single comparison of two elements $a_{i}$ and $a_{j}$ — i.e. the question "is $a_{i} < a_{j}$ ?". (b) A leaf is one output permutation — the ordering the algorithm commits to once it reaches that leaf. Each internal node has 2 children, because the comparison "is $a_{i} < a_{j}$ ?" has exactly two outcomes (yes/ $<$ , or no/ $\geq$ ). That two-ness is the whole reason the tree is binary, and why height $h$ (the longest root-to-leaf path, from the reminder above) allows at most $2^{h}$ leaves.

Level 2 — Application

(Plug numbers into $2^{h} \geq n!$ .)

Recall Solution 2.1

We need enough leaves: leaves $\geq 4! = 24$ . A tree of height $h$ has at most $2^{h}$ leaves, so we need $2^{h} \geq 24 ⟹ h \geq lo g_{2} 24 \approx 4.585 ⟹ h \geq ⌈ 4.585 ⌉ = 5.$ $2^{4} = 16 < 24$ , so height 4 is impossible; $2^{5} = 32 \geq 24$ is feasible. Minimum worst-case comparisons $= 5$ . (And indeed an optimal 4-element sort achieves exactly 5.)

Recall Solution 2.2

$5! = 120$ . So $⌈ lo g_{2} 120 ⌉ = ⌈ 6.907 ⌉ = 7$ . The bound forces height $\geq 7$ . But it does not guarantee a tree of height exactly 7 exists — the bound is necessary, not automatically sufficient. (In fact, for $n = 5$ the optimal is 7, so here they coincide, but for e.g. $n = 12$ the true optimum exceeds $⌈ lo g_{2} n!⌉$ .)

Recall Solution 2.3

Need leaves $\geq 8! = 40320$ . With height 9: $2^{9} = 512 ≪ 40320$ . Since $512 < 40320$ , a height-9 tree can distinguish at most 512 orderings, far short of the 40320 required. The claim is impossible. You need $h \geq ⌈ lo g_{2} 40320 ⌉ = ⌈ 15.3 ⌉ = 16$ comparisons.

Level 3 — Analysis

(Reason about the tree's shape and the bound's structure.)

Recall Solution 3.1

$lo g_{2} (n!)$ (blue) is the true information content — the exact minimum height.
$n lo g_{2} n$ (yellow) is the leading term of Stirling's Approximation. The key fact inline: Stirling says $lo g_{2} (n!) = n lo g_{2} n - n lo g_{2} e + O (lo g n)$ , where $lo g_{2} e \approx 1.4427$ . So the gap between the blue and yellow curves is $\approx 1.44 n$ — linear, hence swallowed by the $n lo g n$ term for large $n$ : the curves hug each other.
$\frac{n}{2} lo g_{2} \frac{n}{2}$ (red) is the crude bound: keep only the top half of the factors of $n!$ , each $\geq n /2$ , so $n! \geq (n /2)^{n /2}$ and $lo g_{2} (n!) \geq \frac{n}{2} lo g_{2} \frac{n}{2}$ . It sits below $lo g_{2} (n!)$ (we threw factors away) but still grows as a constant times $n lo g n$ .

" $Ω (n lo g n)$ " (from the reminder: a lower bound up to a constant factor) only asks for some positive constant $c$ with $lo g_{2} (n!) \geq c n lo g n$ for large $n$ . The crude red curve already delivers such a $c$ (roughly $1/2$ ). So even the wasteful bound proves the theorem — we never needed Stirling for the lower bound, only for the sharp constant.

Recall Solution 3.2

False, in general. A complete balanced tree of height $h$ has exactly $2^{h}$ leaves, yes. But a valid sorting tree needs exactly $n!$ leaves, and $n!$ is almost never a power of 2 (only $n \leq 2$ ). So the minimum-height tree cannot be perfectly balanced — some root-to-leaf paths are shorter than $h$ . The bound uses only the inequality leaves $\leq 2^{h}$ ; it never claims the tree is full — the "used $\leq$ , not $=$ " subtlety.

Recall Solution 3.3

A ternary tree of height $h$ has at most $3^{h}$ leaves. Combining with leaves $\geq n!$ : $3^{h} \geq n! ⟹ h \geq lo g_{3} (n!) = \frac{l o g _{2} ( n !)}{l o g _{2} 3} .$ Since $lo g_{2} 3 \approx 1.585$ is a constant, $lo g_{3} (n!) = Θ (lo g_{2} (n!)) = Θ (n lo g n)$ (recall $Θ$ ignores constant factors). The asymptotic bound is unchanged — only the constant shrinks by a factor $lo g_{2} 3$ . Any fixed number of outcomes per node gives the same $Ω (n lo g n)$ .

Level 4 — Synthesis

(Combine the model with other ideas.)

Recall Solution 4.1

Model the search as a binary decision tree where each internal node compares the target to some array element. Now the possible outcomes are the positions the target could occupy — there are $n + 1$ of them (before element 1, between 1 and 2, …, after element $n$ ). So we need $leaves \geq n + 1, 2^{h} \geq n + 1 ⟹ h \geq lo g_{2} (n + 1) = Ω (lo g n) .$ The difference from sorting: searching has $\sim n$ outcomes, so $lo g_{2} n$ questions; sorting has $n!$ outcomes, so $lo g_{2} (n!) \approx n lo g_{2} n$ questions. Binary Search achieves $⌈ lo g_{2} (n + 1)⌉$ , hence is optimal. This is exactly the classic "Height $\geq lo g_{2} n$ , not $lo g_{2} n!$ " confusion — the mistake was using the search count for the sort problem.

Recall Solution 4.2

Key fact inline (from Information Theory & Entropy): a uniform distribution over $M$ equally-likely outcomes has entropy $H = lo g_{2} M$ bits — the average number of yes/no questions to identify one outcome. Here $M = n!$ , so $H = lo g_{2} (n!) bits .$ To output the correct permutation with certainty, the algorithm must resolve all $H$ bits. Each comparison returns one of two outcomes, giving at most 1 bit. So the number of comparisons in the worst case is $\geq H = lo g_{2} (n!)$ — the same bound, now read as "you can't extract more bits than you ask for." For $n = 6$ : $6! = 720$ , so $H = lo g_{2} 720 \approx 9.492$ bits, i.e. at least $⌈ 9.492 ⌉ = 10$ comparisons.

Recall Solution 4.3

The result is one sorted list of $2 m$ elements; the "unknown" is how the two lists interleave. The number of interleavings is $(m 2 m)$ (choose which $m$ of the $2 m$ output slots hold the first list's elements — see the figure above). So $2^{h} \geq (m 2 m) ⟹ h \geq lo g_{2} (m 2 m) .$ Using $(m 2 m) \geq \frac{2 ^{2 m}}{2 m + 1}$ (a standard bound), $lo g_{2} (m 2 m) \geq 2 m - lo g_{2} (2 m + 1) = Ω (m)$ . So merging needs $Ω (m)$ comparisons — matching the $Θ (m)$ merge step inside Merge Sort.

Level 5 — Mastery

(Build and defend a bound from scratch.)

Recall Solution 5.1

Fact (balanced-tree / Kraft bound): In any binary tree with $L$ leaves at depths $d_{1}, \dots, d_{L}$ , the average depth $\overset{ˉ}{d} = \frac{1}{L} \sum_{i} d_{i} \geq lo g_{2} L$ . (Intuition: a tree can't beat the perfectly balanced one, whose every leaf is at depth $lo g_{2} L$ ; making some leaves shallower forces others deeper by more.)

Apply with $L = n!$ . Assuming each of the $n!$ inputs is equally likely, the average number of comparisons equals the average leaf depth $\overset{ˉ}{d}$ : $\overset{ˉ}{d} \geq lo g_{2} (n!) \geq \frac{n}{2} lo g_{2} \frac{n}{2} = Ω (n lo g n) .$ So even on average, comparison sorting costs $Ω (n lo g n)$ . This closes the caveat that "a lucky input can finish in $O (n)$ " — most inputs cannot; the lucky ones are a vanishing fraction.

Recall Solution 5.2

Each median query has 3 outcomes, so after $q$ queries the tree has at most $3^{q}$ leaves. We still must distinguish all $n!$ orderings: $3^{q} \geq n! ⟹ q \geq lo g_{3} (n!) = \frac{l o g _{2} ( n !)}{l o g _{2} 3} = Ω (n lo g n) .$ Same asymptotic wall — a constant-outcome oracle can shave the constant (here by $1/ lo g_{2} 3 \approx 0.63$ ) but never the $n lo g n$ growth. The lesson: only queries whose number of outcomes grows with the data can break the bound.

Recall Solution 5.3

Proof: (1) need $\geq n!$ leaves (one per output permutation); (2) a binary tree of height $h$ has $\leq 2^{h}$ leaves; (3) so $2^{h} \geq n!$ , giving $h \geq lo g_{2} (n!)$ ; (4) $lo g_{2} (n!) \geq \frac{n}{2} lo g_{2} \frac{n}{2} = Ω (n lo g n)$ . (a) Heapsort runs in $O (n lo g n)$ comparisons — it meets the lower bound, so it's asymptotically optimal. (b) Radix sort isn't a comparison sort (it buckets by digit value), so the model's premise fails and it may run in $O (n)$ without contradiction. Numbers: $10! = 3628800$ . $lo g_{2} (3628800) \approx 21.79$ , so $⌈ \cdot ⌉ = 22$ . Crude bound $\frac{10}{2} lo g_{2} \frac{10}{2} = 5 lo g_{2} 5 \approx 5 (2.3219) = 11.61$ . Note $11.61 \leq 21.79$ — the crude bound is genuinely below the true value yet still $Ω (n lo g n)$ . ✔

Recall One-line summary to carry away

Count the distinct correct answers your tree must reach; take $lo g_{2}$ ; that's your lower bound. For sorting it's $lo g_{2} (n!) = Ω (n lo g n)$ .