Decision Tree | Information Theory | Omega(n log n)
Graduate
Section 1 -- Interactive Simulation
Ready. Press Play or Next.
Speed:
0
Operations
0
Comparisons
0/0
Step
--
n
n: 8
LOWER BOUND PROOF (Decision Tree):
1. Any comparison sort = a binary decision tree
Each internal node: comparison A[i] vs A[j]
Each leaf: one permutation (sorted order)
2. A decision tree for n elements must have
at least n! leaves (one per permutation)
3. A binary tree of height h has at most 2^h leaves
4. Therefore: 2^h >= n!
=> h >= log2(n!)
5. By Stirling: log2(n!) = Theta(n log n)
6. Therefore: any comparison sort needs Omega(n log n) comparisons
Section 2 -- The Idea, Step by Step
Think of sorting as a guessing game. You are handed $n$ shuffled cards, and the only move allowed is to point at two of them and ask "which is larger?" Each answer is a single yes/no clue. The deep question is not how to sort, but how few clues could ever be enough. That unavoidable minimum is what we mean by a "lower bound" -- a wall that no comparison sort, however clever, can get under.
Count what you must tell apart. With $n$ different cards there are $n!$ (n factorial $= n\times(n-1)\times\cdots\times1$) possible starting orders. A correct sort has to distinguish every single one: if two different scrambles ever looked identical to the algorithm, it would hand back the same answer for both and be wrong on at least one. So all $n!$ cases must end up at different places.
Turn questions into a tree. Picture each comparison as a fork in a road map -- one question, two branches (yes / no). After $h$ questions you can reach at most $2^h$ different endpoints. To separate all $n!$ cases you need at least that many endpoints, so $2^h \ge n!$, which rearranges to $h \ge \log_2(n!)$. For $n=8$ that is $\log_2(40320)\approx 15.3$, so no comparison sort can promise fewer than 16 comparisons on 8 items.
Read off the growth rate. Stirling's approximation turns the messy factorial into a clean rate: $\log_2(n!) = n\log_2 n - n\log_2 e + O(\log n)$, which grows like $\Theta(n\log n)$. The information-theory view says the same thing: pinning down one permutation out of $n!$ equally likely ones takes $\log_2(n!)$ bits, and one comparison reveals at most one bit -- so at least $\log_2(n!)$ comparisons are forced. This is why Merge Sort and Heap Sort, at $O(n\log n)$, are asymptotically optimal, and why Counting and Radix Sort can go faster: they read element values instead of only comparing, stepping outside the decision-tree model entirely.
Try this in the sim above. Drag the $n$ slider and watch the Comparisons counter climb, then compare it with the floor $\log_2(n!)$: you will see this bubble-sort visualizer uses far more than the floor (bubble sort is not optimal) -- the lower bound only forbids using fewer. Switch the preset to "Sorted" and notice the comparison count barely drops, a reminder that the bound is about the worst case, not lucky inputs. Then push $n$ to its maximum and watch the count balloon much faster than $n\log_2 n$, the rate an optimal sort would hold to.
Section 3 -- Complexity Analysis
Symbol
Meaning
n
Input size
T(n)
Time complexity
V,E
Vertices and Edges
W
Weight or capacity
Step 1 -- Decision Tree Model. Any deterministic comparison sort can be represented as a binary decision tree. Internal nodes = comparisons. Branches = outcomes (<= or >). Leaves = sorted permutations. The tree must be correct for ALL inputs.
Step 2 -- Number of Leaves. For n distinct elements: n! possible permutations, each requiring a distinct leaf. The decision tree must have at least n! leaves (otherwise two distinct inputs map to the same leaf -- contradiction, since different inputs need different output orderings).
Step 3 -- Height and Leaf Count. A binary tree with L leaves has height h >= ceil(log_2(L)). Since L >= n!: h >= log_2(n!) >= log_2((n/e)^n) = n*log_2(n/e) = n*log_2(n) - n*log_2(e) = Omega(n log n).
Step 5 -- Tight Bound. The lower bound Omega(n log n) is tight: Merge Sort, Heap Sort achieve O(n log n) worst case. These algorithms are asymptotically optimal among comparison sorts.
Step 6 -- Non-comparison Sorts Beat the Bound. Counting Sort, Radix Sort, and Bucket Sort are NOT comparison sorts -- they don't only compare elements. They use element VALUES directly (as array indices). These can achieve O(n) or O(n log k) by exploiting structure beyond comparisons. This does NOT contradict the Omega(n log n) lower bound.
Section 4 -- FAQ
What is the decision tree model? concept+
Model any comparison sort as a binary tree: each internal node asks 'is A[i] <= A[j]?', left subtree for yes, right for no. Each leaf gives the sorted order. The tree must correctly sort ALL possible inputs. This model captures the information extracted by comparisons.
Why must there be at least n! leaves? concept+
For n distinct elements, there are n! possible input orderings. A correct sort must distinguish ALL of them. Two different orderings reaching the same leaf would mean the algorithm gives the SAME output for two different inputs -- at least one would be wrong. So at least n! leaves are needed.
Does Omega(n log n) apply to average case? complex+
The decision tree lower bound gives WORST-CASE Omega(n log n). Average case: by counting, any algorithm averaging less than log_2(n!) comparisons must give wrong answer on some inputs. Since avg over all permutations of (comparisons) >= log_2(n!) (information-theoretic), the AVERAGE case is also Omega(n log n).
Why can Radix Sort be O(n) without violating the lower bound? concept+
The lower bound applies only to COMPARISON sorts. Radix Sort uses element VALUES as array indices -- extracting digits and bucketing. It uses O(n*d) operations that are NOT comparisons between elements. The decision tree model does not apply.
What is the information-theoretic argument? nonobv+
Information theory perspective: n! possible permutations, each equally likely. We need ceil(log_2(n!)) bits of information to identify the correct permutation. Each comparison provides at most 1 bit. Therefore: at least log_2(n!) comparisons needed = Omega(n log n).
Can we do better with non-uniform probability distributions? deep+
If input distribution is known and non-uniform: expected comparisons can be less than log_2(n!). Huffman-optimal sorting uses expected O(H) comparisons where H = entropy of distribution over n! permutations. For near-sorted inputs (low entropy): InsertionSort O(n+inversions) = O(n) for sorted input. Adaptive sorts exploit this.
Section 5 -- Misconceptions
Conceptual
X Omega(n log n) means all sorts must take n log n time.
O Omega(n log n) applies only to COMPARISON SORTS. Non-comparison sorts (Counting, Radix, Bucket) can achieve O(n) by using element values beyond just comparisons.
X Merge Sort is optimal because it is O(n log n).
O Merge Sort is optimal in the worst-case complexity sense -- it matches the Omega(n log n) lower bound. But 'optimal' constants matter: Mergesort has ~n log n comparisons, QuickSort averages ~1.39n log n but is faster in practice due to cache effects.
X The lower bound proves no sorting algorithm can be faster.
O Lower bound for COMPARISON-based model. New computational models (e.g., word RAM with SIMD operations) can sort faster. Integer sorting on word RAM: O(n log log n) deterministic (Han 2002). Theoretical but impractical.
Implementation
X A decision tree with n! leaves has height exactly log2(n!).
O Height >= log2(n!) (floor). May be larger. A balanced tree achieves height ceil(log2(n!)). Actual sort algorithms may have larger trees.
X The lower bound applies to randomized sorting algorithms.
O The Omega(n log n) lower bound applies to deterministic comparison sorts. For randomized algorithms, it also holds for expected number of comparisons -- the lower bound is information-theoretic and applies to any algorithm.
X n! leaves means n! different paths through the tree.
O n! leaves means n! distinct outputs (permutations). The number of paths from root to leaves equals the number of leaves in a binary tree. Each path corresponds to a sequence of comparison outcomes for one specific input permutation.