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

This page is the "hit every case" companion to the parent proof. There we built the whole argument once: $n!$ orderings must each land on a distinct leaf, a binary tree of height $h$ has at most $2^{h}$ leaves, so $2^{h} \geq n!$ and $h \geq lo g_{2} (n!)$ , which grows like $n lo g n$ . Here we stress-test that machinery on every kind of input it can meet — tiny $n$ , degenerate $n$ , huge $n$ , non-comparison sorts that dodge it, and exam twists.

The scenario matrix

Every worked example below is tagged with the matrix cell it covers. The goal: no cell left unvisited.

Cell	Case class	What breaks / is special	Example
A	Smallest non-trivial $n$ ( $n = 2, 3$ )	tree height is an exact small integer	Ex 1
B	Degenerate $n$ ( $n = 0, n = 1$ )	$n! = 1$ , height $0$ — no comparison needed	Ex 2
C	Medium $n$ where $⌈ lo g_{2} n!⌉$ beats the crude $\frac{n}{2} lo g_{2} \frac{n}{2}$	exact vs. loose bound	Ex 3
D	Large $n$ (asymptotic)	Stirling's tight constant $1.44 n$	Ex 4
E	Upper meets lower (optimality)	merge/heapsort are provably best	Ex 5
F	Bound does not apply (non-comparison sort)	premise broken → escape	Ex 6
G	Word problem (real world)	blindfold card game / tournament	Ex 7
H	Exam twist — partial info / duplicates	fewer than $n!$ outcomes → smaller bound	Ex 8

Example 1 — Cell A: the smallest trees that can sort 2 and 3 items

Worked example

$n = 2$ , then $n = 3$ : what is the minimum worst-case number of comparisons in each? Forecast: Guess both now. Binary-search instinct says " $lo g_{2} 3 \approx 1.6$ , so 2 for three items." Hold that thought.

Step 1 — Warm up with $n = 2$ . Two distinct items have $2! = 2$ orderings ( $a < b$ or $a > b$ ). We need $2^{h} \geq 2$ , so $h \geq ⌈ lo g_{2} 2 ⌉ = 1$ . Why this step? One single comparison " $a : b$ " already splits the two orderings into two leaves — a height- $1$ tree with $2$ leaves is exactly enough. This is the smallest case where any comparison happens at all, so it anchors the pattern before we scale up.

Step 2 — Now $n = 3$ : count the outcomes. $3! = 6$ orderings. Why this step? The leaves must cover every possible correct answer; the number of correct answers is $n!$ , not $n$ .

Step 3 — Turn "6 leaves" into a height requirement. We need $2^{h} \geq 6$ . Why this step? A binary tree of height $h$ holds at most $2^{h}$ leaves (Step 2 of the parent proof). To fit 6 leaves we need at least that many slots.

Step 4 — Solve. $2^{2} = 4 < 6$ but $2^{3} = 8 \geq 6$ , so $h \geq ⌈ lo g_{2} 6 ⌉ = 3$ . Why this step? Height must be a whole number of comparisons; $lo g_{2} 6 \approx 2.585$ rounds up to $3$ .

Verify: For $n = 2$ , one comparison suffices ( $⌈ lo g_{2} 2 ⌉ = 1$ ). For $n = 3$ , a height-2 tree has $\leq 4$ leaves — it literally cannot name 6 different orderings, so at least two inputs would get the same (wrong) answer. The figure below makes this forcing visible. And indeed the textbook optimal 3-element sort takes exactly 3 comparisons in the worst case. Your forecast of 2 for three items was the classic trap. ✔

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

Example 2 — Cell B: the degenerate cases $n = 0$ and $n = 1$

Worked example How many comparisons to "sort" an empty list, or a one-element list?

Forecast: Feels like a trick. Zero?

Step 1 — Plug into $n!$ . $0! = 1$ and $1! = 1$ (an empty line and a single item each have exactly one arrangement). Why this step? The bound counts outcomes. If there's only one possible answer, there is nothing to distinguish.

Step 2 — Height requirement. $2^{h} \geq 1 \Rightarrow h \geq lo g_{2} 1 = 0$ . Why this step? $2^{0} = 1$ , so a tree of height $0$ (just a leaf, no comparisons) already suffices.

Step 3 — Read it as an algorithm. With $0$ or $1$ elements you output the input unchanged, asking zero comparisons. Why this step? The lower bound is $0$ ; the actual work is $0$ ; they match — the theorem is silent (and correct) here.

Verify: $⌈ lo g_{2} 1 ⌉ = 0$ . No contradiction with " $Ω (n lo g n)$ " because $Ω$ describes growth as $n \to \infty$ ; it never claims anything about a fixed tiny $n$ . ✔

Example 3 — Cell C: exact bound vs. the crude bound at $n = 8$

Worked example For

$n = 8$ , compare the true minimum height with the loose $\frac{n}{2} lo g_{2} \frac{n}{2}$ estimate. Forecast: Guess whether the crude estimate is close or badly loose.

Step 1 — Exact requirement. $8! = 40320$ . We need $2^{h} \geq 40320$ , so $h \geq ⌈ lo g_{2} 40320 ⌉$ . Why this step? This is the honest information-theoretic floor — no approximation yet.

Step 2 — Evaluate the log. $2^{15} = 32768 < 40320 < 65536 = 2^{16}$ , so $lo g_{2} 40320 \approx 15.30$ and $⌈ \cdot ⌉ = 16$ . Why this step? Round up: you cannot ask $15.3$ questions.

Step 3 — Crude lower bound from the parent. $\frac{n}{2} lo g_{2} \frac{n}{2} = 4 \cdot lo g_{2} 4 = 4 \cdot 2 = 8$ . Why this step? The parent threw away the small factors $1, 2, 3$ to get an easy bound. That discarding costs accuracy.

Verify: True floor $= 16$ ; crude bound $= 8$ . Both are valid lower bounds ( $16 \geq 8 \geq 0$ ), but the crude one is half the truth — that's the price of the clean $(\frac{n}{2})^{n /2}$ trick. It still grows like $n lo g n$ , which is all we needed asymptotically. ✔

Example 4 — Cell D: large $n$ and Stirling's tight constant

Worked example Estimate

$lo g_{2} (n!)$ for $n = 1000$ using Stirling's Approximation, and read off the leading constant. Forecast: Will it be closer to $1000 \cdot 10 = 10000$ , or noticeably less?

Step 0 — One new symbol first: $ln$ . Alongside $lo g_{2}$ (base 2), we now meet $ln x$ , the natural logarithm — the same "to what power?" question but with base $e \approx 2.718$ instead of $2$ . So $ln x$ answers " $e$ to what power gives $x$ ?" We only need one fact linking them: to change from base $e$ to base $2$ , divide by $ln 2 \approx 0.693$ , i.e. $lo g_{2} x = \frac{ln x}{ln 2}$ . Stirling's formula is naturally written in $ln$ , so we translate at the end. Why introduce $ln$ here? Stirling's Approximation is stated in the natural log; refusing to use it would mean re-deriving the constant from scratch. Borrowing $ln$ and converting is the honest, short route.

Step 1 — State the tool. Stirling's Approximation gives $ln (n!) \approx n ln n - n$ . Converting to base 2 (divide by $ln 2$ ): $lo g_{2} (n!) \approx n lo g_{2} n - n lo g_{2} e, lo g_{2} e \approx 1.4427.$ Why this tool and not the crude bound? The $(\frac{n}{2})^{n /2}$ trick loses a factor of 2. Stirling captures the exact leading term $n lo g_{2} n$ plus the honest linear correction $- 1.44 n$ . When we claim merge sort is optimal to the constant, we need this precision.

Step 2 — Plug $n = 1000$ . $lo g_{2} 1000 \approx 9.966$ . $lo g_{2} (1000!) \approx 1000 (9.966) - 1000 (1.4427) \approx 9966 - 1443 = 8523.$ Why this step? Both terms scale with $n$ ; the $- 1.44 n$ correction is a real 15% shave off the naive $n lo g_{2} n$ .

Step 3 — Interpret. So some input of 1000 items forces at least $\approx 8523$ comparisons. Why this step? It converts an abstract lower bound into a concrete floor a machine must pay.

Verify: A direct computation of $lo g_{2} (1000!)$ gives $\approx 8529.4$ ; our Stirling estimate $8523$ is within $0.1%$ . The leading constant is $1$ (coefficient of $n lo g_{2} n$ ), confirming merge sort's $n lo g_{2} n$ is tight to the constant, not just the order. ✔

Example 5 — Cell E: upper bound meets lower bound (optimality)

Worked example

Merge Sort does $\leq n ⌈ lo g_{2} n ⌉$ comparisons. Show it is asymptotically optimal for $n = 16$ . Forecast: Will merge sort's cost sit near the lower-bound floor or far above it?

Step 1 — Lower bound (floor). $16! \approx 2.09 \times 1 0^{13}$ . $lo g_{2} (16!) = ⌈ 44.25 ⌉ = 45$ comparisons minimum. Why this step? This is the wall no comparison sort can cross.

Step 2 — Upper bound (merge sort ceiling). $n ⌈ lo g_{2} n ⌉ = 16 \cdot 4 = 64$ comparisons. Why this step? This is a concrete algorithm we can actually run — an upper bound on what's achievable.

Step 3 — Sandwich. $45 \leq (true optimum) \leq 64$ . Both are $Θ (n lo g n) = Θ (16 \cdot 4)$ . Why this step? Lower bound and upper bound have the same growth order, so the comparison complexity of sorting is exactly $Θ (n lo g n)$ — merge sort is optimal up to a constant factor. The same holds for Heapsort.

Verify: $45$ and $64$ differ by a factor of $1.42 < 2$ — a bounded constant, not a growing gap. No hypothetical sort growing like $n lo g lo g n$ can exist, since it would eventually dip below the $lo g_{2} (n!)$ floor. ✔

Example 6 — Cell F: escaping the bound (non-comparison sort)

Worked example

Counting Sort sorts $n = 1000$ integers drawn from the range $[0, 500)$ in $O (n + k)$ time. Does it violate the $Ω (n lo g n)$ floor? Forecast: It runs in $\approx 1500$ steps — far below the $8523$ floor from Example 4. Contradiction?

Step 0 — Define $k$ . Here $k$ is the size of the key range — the number of distinct integer values a key could take. Counting sort of values in $[0, 500)$ uses a tally array of length $500$ , so $k = 500$ . Its running time $O (n + k)$ (recall $O (\cdot)$ = "grows no faster than", from the definition box up top) means: roughly $n$ steps to scan the input plus $k$ steps to sweep the tally array. Why define $k$ first? The bound $O (n + k)$ is meaningless until you know what $k$ counts; it is the value-range size, a completely different quantity from $n$ (the number of items).

Step 1 — Check the premise. The theorem's hypothesis is "the algorithm uses only comparisons $a_{i} : a_{j}$ ." Why this step? A theorem only binds objects that satisfy its assumptions. Break the assumption, and the conclusion need not hold.

Step 2 — Inspect counting sort. It does count[x] += 1 — it uses the value $x$ as an array index. That is arithmetic on the value, not a comparison. Why this step? This single line means counting sort is not modelled by any decision tree of comparisons; the $2^{h}$ argument never applies to it.

Step 3 — Reconcile the numbers. Counting sort's cost $O (n + k)$ with $n + k = 1500$ beating $8523$ is fine; there was never a wall in front of it. The same for Radix Sort. Why this step? Removes the apparent paradox: $8523$ bounds comparison sorts only.

Verify: $n + k = 1000 + 500 = 1500 < 8523$ . No contradiction — the floor bounds a different class of algorithms. This is why value-based sorts exist. ✔

Example 7 — Cell G: the blindfold card word problem

Worked example You are blindfolded with 5 shuffled cards. Your only move is to ask a friend "is card

$i$ below card $j$ ?" (yes/no). What is the guaranteed-minimum number of questions to always determine the full order? Forecast: Five cards — guess a number between 4 and 10.

Step 1 — Model it. Each yes/no question = one comparison = one internal node. A strategy = a decision tree. The full order is one of $5! = 120$ arrangements. Why this step? "Blindfold + yes/no only" is exactly the comparison model — the word problem is the theorem in disguise.

Step 2 — Apply the floor. $2^{h} \geq 120 \Rightarrow h \geq ⌈ lo g_{2} 120 ⌉$ . Why this step? $h$ questions distinguish at most $2^{h}$ situations.

Step 3 — Evaluate. $2^{6} = 64 < 120 < 128 = 2^{7}$ , so $lo g_{2} 120 \approx 6.907$ , ceiling $= 7$ . Why this step? You cannot ask $6.9$ questions; round up. At least 7 questions are unavoidable in the worst case.

Verify: $⌈ lo g_{2} 120 ⌉ = 7$ . (Six questions give only 64 distinguishable outcomes — not enough for 120 shuffles.) A known optimal 5-element sort uses exactly 7 comparisons, so the floor is achieved, not merely approached. ✔

Example 8 — Cell H: exam twist — duplicates shrink the bound

Worked example Exam twist: you sort

$n = 4$ items, but you're told two of them are equal and the other two are distinct (multiset ${a, a, b, c}$ ). How many distinguishable outputs are there, and what is the comparison floor? Forecast: Still $4! = 24$ ? Or fewer because some arrangements look identical?

Step 1 — Count distinguishable outcomes. With a repeated element, swapping the two equal copies produces the same sorted sequence. Distinct arrangements $= \frac{4 !}{2 !} = \frac{24}{2} = 12$ . Why this step? The bound is $lo g_{2} (number of distinct correct outputs)$ . Identical outputs don't need separate leaves — the $n!$ count assumed all distinct keys.

Step 2 — Apply the floor. $2^{h} \geq 12 \Rightarrow h \geq ⌈ lo g_{2} 12 ⌉$ . Why this step? Fewer outcomes ⇒ fewer leaves needed ⇒ potentially shorter tree.

Step 3 — Evaluate. $2^{3} = 8 < 12 < 16 = 2^{4}$ , so $lo g_{2} 12 \approx 3.585$ , ceiling $= 4$ . Why this step? Round up: at least 4 comparisons, versus $⌈ lo g_{2} 24 ⌉ = 5$ for four distinct keys.

Verify: $⌈ lo g_{2} 12 ⌉ = 4$ and $⌈ lo g_{2} 24 ⌉ = 5$ : duplicates genuinely lower the information floor by one comparison here. Lesson: the bound is $lo g_{2} (distinct outputs)$ , and $n!$ is just its value when all keys differ. ✔

Recall The one habit that fixes every case

Always ask first: "How many distinct correct outputs are possible?" Call it $L$ . Then the worst-case comparison floor is $⌈ lo g_{2} L ⌉$ .

All distinct keys → $L = n!$ → grows like $n lo g n$ .
Duplicates → $L = \frac{n !}{( repeats )!}$ → smaller floor.
$n \leq 1$ → $L = 1$ → floor $0$ .
Not comparison-only → the model doesn't apply, no floor at all.

Recall Self-test

Why does a repeated key lower the bound but counting sort remove it entirely? ::: Repeats cut $L$ (fewer leaves needed) but you're still comparison-only, so a floor $⌈ lo g_{2} L ⌉$ remains; counting sort abandons comparisons altogether, so no decision-tree floor applies. Minimum worst-case comparisons to sort 5 distinct items? ::: $⌈ lo g_{2} 120 ⌉ = 7$ .

Related tools used above: Big-O and Asymptotic Notation, Information Theory & Entropy, Binary Search, Quicksort.