Maths/Big O notation

Lower bound proofs

After thiswhat you will be able to doProve that every comparison sort needs Omega(n log n) comparisons in its worst case by counting leaves in its decision tree.

Questionwhat this lesson answersA lower bound on one algorithm says that algorithm cannot do better. A lower bound on a problem says no algorithm can, including ones nobody has written yet. How do you prove the second kind, that every possible method must do at least a certain amount of work?

Not coveredwhat this lesson leaves outWe prove one problem lower bound, that comparison sorting needs at least about n log n comparisons, by a counting argument. We do not prove lower bounds outside the comparison model, and we do not use the exact factorial estimate, only the bound it gives.

The Upper, lower, and tight lesson made an easy-to-miss distinction. Choose one algorithm, look at its slowest input of each size, and show that its work never drops below a certain rate. That is a lower bound on that algorithm. It tells us something real, but a different algorithm might avoid the work altogether.

The stronger claim starts with the problem instead. A problem lower bound says that every possible method must pay a certain cost, including methods nobody has invented. It cannot come from taking apart one program, because one program is only one candidate. The question is what every candidate has in common that forces the work.

First fix what kind of work is allowed. Imagine a sorting method that knows nothing useful about its items except the answer to a question such as “is this item before that item?” We count only those two-item questions. This restriction is called the comparison model, and a sorting method inside it is called a comparison sort. We will sort distinct items, so each question has two outcomes rather than an equality case.

Put ${n}$ distinct items in a row. There are many possible ways for their relative order to turn out. Start by choosing the first position in ${n}$ ways, then the next in one fewer ways, and keep going until only one choice remains. This count of all distinct orderings is called n factorial, written ${n!}$:

For eight items, the number is already much larger than eight:

A sorting method has to be able to finish correctly for every one of those orderings. Any one of them could be the true order of the input items. The method therefore has to tell them apart. It does not matter whether its author calls it quick, clever, or new. If it works only by asking comparisons, its answers must contain enough information to separate all of the possibilities.

Picture one run of the method as a path. Each comparison sends the run one way when the first item comes earlier and the other way when it comes later. Put a branch at every such question and an ending at every possible final ordering. This branching record is called a decision tree. One ending is called a leaf. A correct comparison sort needs a different leaf for every ordering it can be asked to produce. Two inputs that answer every comparison the same way follow the same path to the same leaf and receive the same output, so if two different orderings shared a leaf the method would misreport at least one of them.

Suppose the longest path has ${d}$ comparisons. This number of comparisons along a path is called its depth. A structure that can split in two at each of ${d}$ levels has at most ${2^d}$ leaves. To hold a leaf for each of the ${n!}$ orderings, its worst-case depth has to satisfy

Taking the base-two logarithm turns the condition around:

The logarithm is not a decoration. It counts how many two-way splits are needed before there can be enough endings. For eight items, the number is just above fifteen, so a whole comparison count must round up:

The number on the right grows with the familiar combined shape. Taking a logarithm of the product turns the factors in ${n!}$ into a sum. No factor contributes more than ${\log_2 n}$, while at least half the factors are at least ${\dfrac{n}{2}}$. Those two facts trap the sum between fixed multiples of ${n \log_2 n}$ once the input is large enough. The exact factorial estimate is left alone here; the useful result is

So every comparison sort has a worst case that needs at least the ${n \log n}$ shape of comparisons:

This is a lower bound over every comparison sort at once. It did not inspect insertion sort, merge sort, or a hypothetical method waiting to be written. It counted what any method in the model must distinguish. The Recurrence relations lesson showed merge sort using about ${n \log_2 n}$ comparisons. Its count has the same growth shape as the unavoidable floor, so no comparison sort can beat merge sort’s growth rate. The Upper, lower, and tight door separates this problem-wide statement from a lower bound about one chosen algorithm. The Logarithms, and why the base stops mattering door explains why the base two in the count does not alter that growth class.

The model boundary matters. This proof counts comparisons, not memory writes, arithmetic, or any other operation. A method allowed to use more than comparisons can sometimes do better. If items are nonnegative whole numbers in a known small range, for example, their values can be used as array positions instead of being compared pair by pair. That is outside the comparison model, so it is not a counterexample to this proof.

The proof shape is worth keeping. An upper bound is shown by exhibiting one method that achieves a cost. A lower bound on a problem is shown by finding a bill every allowed method must pay. Here the bill is the number of possible outcomes that its comparisons have to tell apart.