The Comparison-Sorting Lower Bound
Any sort that only compares pairs of elements is a decision tree with n factorial leaves, so its height is at least n log n. This is a statement about every possible algorithm, not about the ones anybody has written.
What a learner can do afterwards
- Draw the decision tree of a comparison sort on three elements and count its leaves
- Argue from the leaf count to a bound on the tree's height
- Explain how counting sort beats the bound without contradicting it
1 · Read
A comparison sort learns only by comparing pairs of items. Picture its work as a decision tree, where each branch is one compare result and each leaf is one final order.
Take three distinct items. They can arrive in 6 orders, which is 3 factorial, so the tree needs at least 6 leaves, one leaf per order. A tree of height 2 holds at most 4 leaves, so height 2 is not enough.
For n items there are n factorial orders, so any comparison tree needs n factorial leaves. Its height is at least log base 2 of n factorial, which grows like n log n. That height is a floor, called big-Omega, that every comparison sort must reach. Mergesort and heapsort touch that floor, so they are as fast as any comparison sort can ever be.
Counting sort can run faster because it changes the rules and reads values instead of comparing pairs. That beats the floor without breaking it, since the floor only covers comparing sorts.
Comparing sorts need n factorial leaves, so they cost at least n log n, and only non comparing methods can dodge that floor.
More to read
Big-Ω (Big-Omega) notation
Sometimes we want to say that an algorithm takes at least a certain amount of time, not at most. That is what big-Ω, the Greek letter omega, is for. If a running time is Ω(f(n)), then once n gets large enough, the running time is always at least k times f(n) for some constant k. Think of it as a floor the algorithm can never dip below, no matter how clever the programmer is. This idea is exactly what makes the sorting lower bound so powerful. We can prove that ANY sorting algorithm that only compares pairs of elements needs at least k times n log n comparisons. Mergesort and heapsort match that floor, so they are as good as any comparison sort can ever be. Big-Ω lets us say that with full confidence, because it is a statement about every algorithm allowed to play by those rules, not just the ones people have written so far.
Measuring an algorithm's efficiency
A good algorithm gets the right answer. A great algorithm gets the right answer while using as little time and memory as possible. One way to measure efficiency is to count how many operations an algorithm performs as the input grows. Take linear search: it checks a list one item at a time. If the list has n items, it might find the target on the first check or the last, so it takes up to about n comparisons. Counting operations lets us compare two algorithms fairly, without running them on a specific computer. This counting habit leads straight to the lower bound. Take three distinct items. They can arrive in 6 orders (3 factorial), and a comparison sort must tell all 6 apart, so its decision tree needs at least 6 leaves, one per order. A binary tree of height 2 holds at most 4 leaves, so the tree needs height at least 3, meaning some input forces 3 comparisons. The same count scales up: n items have n factorial orders, so any comparison tree needs n factorial leaves, and its height is at least log base 2 of n factorial, which grows like n log n. That count becomes a floor that every comparison based sorter must hit.
The building blocks of algorithms
An algorithm is a step by step process that solves a problem and always gives a correct answer. For most problems there are many possible algorithms, and the best one is usually the fastest. Programmers use algorithms constantly, whether it is a famous one like sorting a list or a brand new one built for one special job. Understanding how algorithms work, and how fast they can possibly be, helps you pick the right tool and avoid wasting effort. That is where lower bounds come in. A lower bound tells you the best speed ANY algorithm for a problem could reach. If you know sorting by comparisons cannot beat n log n, you can stop hunting for a faster comparison sort and instead look for ways to change the rules, like counting sort does when the data allows it.
2 · Watch
Take it off screen
Where it sits
Learn first
Nothing; this is a starting point.
Optional connections
This opens up
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.