Lower Bounds

Discrete Math · Axiom Academy

LESSON Lower Bounds for Sorting Why comparison-based sorting can never be faster than Ω(n log n), and how to beat this bound with counting sort for restricted inputs. A decision tree models all possible execution paths of a comparison-based sorting algorithm: Internal nodes: Represent comparisons between elements (e.g., "a₁ ≤ a₂?") Edges: Represent outcomes (yes/no, true/false) Leaves: Represent final sorted permutations Here's the key insight: for n distinct elements, there are n! possible permutations. Since the algorithm must correctly sort any input, the decision tree must have at least n! leaves—one for each possible output permutation. For 3 elements: 3! = 6 possible orderings For 4 elements: 4! = 24 possible orderings For n elements: n! possible orderings Each leaf must represent a unique permutation, so we need at least n! leaves for the tree to correctly handle all inputs. 3. The Height-Leaves Relationship Now we use a fundamental property of binary trees: a binary tree of height h has at most 2ʰ leaves. Since our decision tree must have at least n! leaves, and a binary tree of height h has at most 2ʰ leaves, we get: Taking logarithms of both sides: Therefore, the height h (worst-case number of comparisons) must be at least log₂(n!). 4. Applying Stirling's Approximation To simplify log₂(n!), we use Stirling's approximation, which tells us that n! grows approximately like (n/e)ⁿ: More precisely, using Stirling: log₂(n!) = Θ(n log n)

This is the written version of the interactive lesson above. See the full Discrete Math course.