The Decision-Tree Lower Bound Proof

Overview

Any comparison-based sorting algorithm must perform $\Omega(n \log n)$ comparisons in the worst case. This is a fundamental lower bound, proved by modelling the algorithm as a decision tree. Non-comparison sorts (counting, radix, bucket) evade this bound because they examine key values directly, not just pairwise orderings.

The Decision Tree Model

A comparison-based sorting algorithm can be modelled as a binary tree:

• Each internal node represents a comparison between two elements: $a_i \le a_j?$
• The two outgoing edges represent the outcomes: Yes (true) and No (false).
• Each leaf represents a specific output permutation of the input — the sorted order.
• A path from root to leaf represents the sequence of comparisons performed for a particular input that yields that sorted permutation.

For inputs with $n$ distinct elements, there are $n!$ possible permutations of the output. Each permutation must be reachable via some path in the decision tree, so the tree must have at least $n!$ leaves.

The Proof

Consider an arbitrary comparison-based sorting algorithm. Let $h$ be the height of its decision tree (the maximum number of comparisons performed on any input of size $n$).

A binary tree of height $h$ has at most $2^h$ leaves (each level at most doubles the number of nodes, and leaves can only appear at the bottom). Since the tree must accommodate all $n!$ possible output orderings:

$n! \le \text{\#leaves} \le 2^h$

Taking logs base 2:

$h \ge \log_2(n!)$

By Stirling’s approximation, $\log_2(n!) = \Theta(n \log n)$. More precisely:

$\log_2(n!) = n \log_2 n - n \log_2 e + \Theta(\log n)$

Therefore $h = \Omega(n \log n)$. Any comparison sort performs $\Omega(n \log n)$ comparisons in the worst case.

The Flaw (Non-Comparison Sorts)

The proof contains a crucial assumption: that the only way to gain information about the input is through pairwise comparisons. This is the comparison model.

Counting sort does not compare elements against each other. Instead, it uses the numeric value of a key as an array index — an operation that is not a comparison. Radix sort similarly uses digit values to route elements into buckets. These operations are not representable as decision-tree nodes of the form $a_i \le a_j$, so the lower bound does not constrain them.

In essence: the lower bound says “if all you can do is compare pairs of elements, you need $\Omega(n \log n)$ comparisons”. Non-comparison sorts sidestep this by exploiting structural properties of the keys (bounded integer range, representable as digits, uniform distribution).

Bubble Sort: A Cautionary Tale

Bubble sort repeatedly scans the array, swapping adjacent elements that are out of order, until a full pass produces no swaps. In the worst case (reverse-sorted input), it performs $\Theta(n)$ passes with $\Theta(n)$ comparisons each, yielding $\Theta(n^2)$ total comparisons.

Bubble sort is a comparison sort and is quadratically slower than the $\Omega(n \log n)$ lower bound permits. It is presented in the course as an example of what not to reinvent. Its saving grace is a nice loop invariant: after the $k$-th pass, the $k$ largest elements are in their final sorted positions.

Significance

The decision-tree lower bound establishes a theoretical limit. It tells us that mergesort and heapsort are asymptotically optimal comparison sorts (both achieve $\Theta(n \log n)$). It also tells us that to beat $n \log n$, we must abandon the comparison model — which counting, radix, and bucket sort all do.

Summary

Property	Value
Lower bound for comparison sorts	$\Omega(n \log n)$
Proof technique	Decision tree with $n!$ leaves
Key inequality	$2^h \ge n! \implies h = \Omega(n \log n)$
Why non-comparison sorts beat it	They examine key values, not just pairwise order
Optimal comparison sorts	Mergesort, Heapsort (both $\Theta(n \log n)$)