Proving a cost cannot be beaten: lower bounds

An upper bound is a promise about every input. A worst-case lower bound needs only one bad input for each size, and finding that family is a skill of its own.

So far every argument has been an upper bound: the procedure does at most this much work. The opposite direction is a different kind of claim and it is argued in a different way. Saying a procedure sometimes does at least this much work is what stops a hopeful reader from believing a faster version exists when it does not.

Start with the practical version of the question. You have timed insertion sort on a few thousand shuffled numbers and it looked acceptable. Is there an input of that size on which it does far more work, and how would you know you had found the worst one rather than merely a bad one?

The way to know is to build the bad input deliberately rather than to search for it. A family of inputs is one input chosen for each size $n$, described by a rule rather than listed. For insertion sort, the family is the array that runs strictly downwards: $n, n-1, \ldots, 2, 1$. Run it and compare the count against $n^2/4$.

What the definition asks for

Write $T_{\text{worst}}(n)$ for the largest number of operations the procedure performs over all inputs of size $n$. The claim $T_{\text{worst}}(n) = \Omega(g(n))$ unfolds, by the definition from two lessons ago, into: there are fixed $c > 0$ and $n_0$ with $T_{\text{worst}}(n) \ge c\,g(n)$ for every $n \ge n_0$.

Now notice what that lets you get away with. $T_{\text{worst}}(n)$ is a maximum, so any single input of size $n$ gives a value that $T_{\text{worst}}(n)$ is at least as large as. One input per size is therefore enough, and that is the whole reason lower bounds on a named algorithm are provable by hand.

The insertion sort bound, every step written out

Take the family $A_n = (n, n-1, \ldots, 2, 1)$, the array of the first $n$ whole numbers in decreasing order. Fix a pass number $i$, somewhere between 1 and $n-1$. The value at position $i$ is $n - i$, and the values at positions 0 to $i-1$ are $n, n-1, \ldots, n-i+1$, every one of them larger than $n - i$.

The inner loop compares the value being placed with the entries to its left and keeps going while they are larger. Since all $i$ of them are larger, it compares against all $i$ and only stops by running off the left end. So pass $i$ costs exactly $i$ comparisons.

Add the passes up. The passes are $i = 1, 2, \ldots, n-1$, and pass $i$ costs $i$, so the total is $1 + 2 + \cdots + (n-1)$, which by the sum from the counting lesson is $\frac{(n-1)n}{2}$. For $n = 64$ that is $\frac{63 \times 64}{2} = 2016$, which is what the snippet printed.

The last inequality deserves its own line. The claim $\frac{(n-1)n}{2} \ge \frac{n^2}{4}$ becomes, after multiplying both sides by 4, $2n(n-1) \ge n^2$, that is $2n^2 - 2n \ge n^2$, that is $n^2 - 2n \ge 0$, that is $n(n-2) \ge 0$. Both factors are non-negative exactly when $n \ge 2$, so the inequality holds from $n = 2$ onwards.

The definition wanted two numbers and now both are in hand: $c = \frac{1}{4}$ and $n_0 = 2$. So $T_{\text{worst}}(n) = \Omega(n^2)$ for insertion sort. Put that beside the upper bound $T_{\text{worst}}(n) = O(n^2)$ proved earlier and the two together give $T_{\text{worst}}(n) = \Theta(n^2)$: the worst case is quadratic, not merely at most quadratic.

A lower bound on the problem, not on one procedure

The bound above is about insertion sort and says nothing about what some cleverer procedure might do. A stronger kind of claim covers every possible algorithm for a task, and the argument for it uses an opponent rather than a family.

Take the maximum problem from the first lesson. The claim is that any correct algorithm must read every one of the $n$ entries, so no algorithm for it can cost less than $\Omega(n)$. Here is a procedure that tries to save one read, and what happens to it.

The general argument is that demonstration with the particular procedure removed. Suppose some algorithm claims to solve the maximum problem and, on the input of $n$ zeros, finishes without ever reading position $j$. Call its answer $v$, which must be 0, since 0 is the maximum of that input.

Now build a second input: $n$ zeros again, except that position $j$ holds 1. Every cell the algorithm reads holds exactly what it held before, because position $j$ is the only cell that changed and that is the one cell it does not read. An algorithm whose every read returns the same value takes the same path and produces the same answer, so it answers 0 again. But the maximum of the second input is 1, so the answer is wrong.

The algorithm was assumed correct, so this cannot happen, and the assumption that it skipped a position must be false. It therefore reads all $n$ positions, which costs at least $n$ operations. With $c = 1$ and $n_0 = 1$ that is exactly $T_{\text{worst}}(n) = \Omega(n)$, and it holds for every algorithm anyone will ever write for this problem.

That kind of opponent, who is allowed to decide what the untouched part of the input holds after seeing what the algorithm did, is called an adversary. The maximum scan from the first lesson costs $n - 1$ comparisons, which is $O(n)$, so the problem's lower bound and that algorithm's upper bound meet. When they meet, the problem is settled and no cleverness can help.