How cost grows

An exact step count is machine-specific and unusable, so the previous lesson ended by throwing away everything except the shape of the growth, and this lesson makes "shape" a definition rather than a gesture.

What the definition has to do

The claim to be formalised is "this cost grows like $n^{2}$ ". Three properties are wanted from it.

It must ignore constant factors, because the constants come from the hardware and the compiler and cannot be defended. It must ignore lower-order terms, because at the sizes where cost matters they contribute a vanishing fraction. And it must be provable, so that a claim can be settled rather than argued about.

The standard device does all three at once. Instead of asking whether two functions are equal, ask whether one is eventually bounded by a multiple of the other. "Eventually" throws away small $n$ , which is where lower-order terms live. "A multiple of" throws away the constant. And both are witnessed by numbers you can write down, which makes the claim checkable.

The notation is Paul Bachmann's, from 1894, popularised in analysis by Edmund Landau and brought into computing by Donald Knuth in a 1976 note that fixed the definitions used here.

Big O: an upper bound

Let $f (n)$ and $g (n)$ be functions from positive integers to non-negative reals. Then

f (n) = O (g (n)) ⟺ \exists c > 0, n_{0} > 0 such that f (n) \leq c g (n) for all n \geq n_{0}

The pair $(c, n_{0})$ is called a witness. To prove a big-O claim you produce one; to refute a claim you show no pair can exist. Nothing else is involved, and in particular no limits are needed.

The equals sign is an abuse of notation that everyone commits and nobody defends. $O (g)$ is really a set of functions, and $f = O (g)$ means $f \in O (g)$ . The abuse is harmless as long as you never read it symmetrically: $n = O (n^{2})$ is true and $O (n^{2}) = n$ is nonsense.

Example. Show that $3 n^{2} + 5 n + 100 = O (n^{2})$ by producing a witness.

The strategy is to bound each term by a multiple of $n^{2}$ . For the middle term, $5 n \leq 0.5 n^{2}$ whenever $n \geq 10$ . For the constant, $100 \leq n^{2}$ whenever $n \geq 10$ . So for all $n \geq 10$ ,

3 n^{2} + 5 n + 100 \leq 3 n^{2} + 0.5 n^{2} + n^{2} = 4.5 n^{2}

The witness is $c = 4.5$ , $n_{0} = 10$ . Check it at the boundary: $f (10) = 300 + 50 + 100 = 450$ and $4.5 \times 100 = 450$ , so the inequality holds with equality there, and at $n = 9$ it fails ( $388 > 364.5$ ), which is why $n_{0}$ could not be smaller for this particular $c$ . Witnesses are never unique: $c = 108$ , $n_{0} = 1$ works too, and is just as valid a proof.

Now you. Produce a witness showing $2 n^{3} + 7 n^{2} + 3 = O (n^{3})$ .

Answer

Bound each term: $7 n^{2} \leq n^{3}$ when $n \geq 7$ , and $3 \leq n^{3}$ when $n \geq 2$ . So for $n \geq 7$ , $2 n^{3} + 7 n^{2} + 3 \leq 2 n^{3} + n^{3} + n^{3} = 4 n^{3}$ , giving the witness $c = 4$ , $n_{0} = 7$ . Checking at $n = 7$ : $686 + 343 + 3 = 1032 \leq 4 \times 343 = 1372$ . The bound in fact holds from $n = 5$ onward, which is fine: a witness only has to work, not to be the smallest.

Omega and Theta: the other two bounds

Big O alone is a weak statement, because it is an upper bound and nothing stops it being loose. Every algorithm in this course is $O (2^{n})$ , and saying so tells you nothing. Two companions fix that.

$f (n) = Ω (g (n))$ if there are $c > 0$ and $n_{0}$ with $f (n) \geq c g (n)$ for all $n \geq n_{0}$ : a lower bound, used to say an algorithm cannot do better than something, and used for problems rather than algorithms when proving that no algorithm can.

$f (n) = Θ (g (n))$ if both hold: there are $c_{1}, c_{2} > 0$ and $n_{0}$ with $c_{1} g (n) \leq f (n) \leq c_{2} g (n)$ for $n \geq n_{0}$ . This is the tight statement, and it is what "grows like" actually means.

So $3 n^{2} + 5 n + 100$ is $Θ (n^{2})$ : the upper witness is above, and for the lower, $3 n^{2} + 5 n + 100 \geq 3 n^{2}$ for every $n \geq 1$ , giving $c_{1} = 3$ , $n_{0} = 1$ . It is also $O (n^{3})$ , truthfully but uselessly, and it is not $Θ (n^{3})$ , because no $c_{1} > 0$ has $3 n^{2} + 5 n + 100 \geq c_{1} n^{3}$ eventually: divide by $n^{3}$ and the left side goes to zero while $c_{1}$ does not.

Refutations work the same way, by contradiction on the witness. Is $n^{2} = O (n)$ ? Suppose a witness $(c, n_{0})$ existed, so $n^{2} \leq c n$ for all $n \geq n_{0}$ . Divide by $n$ : $n \leq c$ for all $n \geq n_{0}$ . But $n$ is unbounded, so take $n = \max (c, n_{0}) + 1$ and the inequality fails. No witness exists.

Prefer $Θ$ wherever you can prove it. Most published results are stated with $O$ out of caution, since an upper bound is what a guarantee needs, but when a source says an algorithm is $O (n \log n)$ and you want to know whether it might secretly be linear, the answer is usually that the author could have written $Θ$ and chose the weaker word.

The hierarchy, priced

Definitions settle arguments; a table shows why anyone cares. Assume a machine performing $10^{9}$ steps per second, which is the right order of magnitude for a single core running simple loop code.

cost	$n = 100$	$n = 1000$	$n = 10^{6}$
$\log_{2} n$	6.6 ns	10.0 ns	19.9 ns
$n$	100 ns	1.0 µs	1.0 ms
$n \log_{2} n$	664 ns	10.0 µs	19.9 ms
$n^{2}$	10.0 µs	1.00 ms	16.7 minutes
$n^{3}$	1.00 ms	1.00 s	31.7 years
$2^{n}$	$4 \times 10^{13}$ years	beyond writing	beyond writing

Read the columns rather than the rows. At $n = 100$ every one of the polynomial costs is imperceptible, and choosing between them is a waste of a morning. At $n = 10^{6}$ the same choices are the difference between an instant response, a coffee break and a career.

The entry worth staring at is $2^{n}$ . At $n = 50$ an exponential algorithm running a billion steps a second takes thirteen days; at $n = 60$ it takes 36.5 years. Ten more items, a factor of a thousand. Buying a machine a thousand times faster buys you ten more items. That is why the last lesson of this course treats exponential cost as a qualitative barrier rather than a large number.

Example. A quadratic algorithm costing exactly $n^{2}$ steps handles $n = 10^{4}$ in 0.1 seconds on a given machine. A colleague proposes running it on $n = 10^{6}$ . How long will that take, and would a machine 100 times faster fix it?

Cost scales as $n^{2}$ , and $n$ grew by a factor of 100, so the work grows by $100^{2} = 10^{4}$ . The time becomes $0.1 \times 10^{4} = 1000$ seconds, about 17 minutes. A machine 100 times faster brings that to 10 seconds, which is a genuine improvement, but note what the same money buys on the input side: at fixed time budget, a machine 100 times faster handles only 10 times the input, since $\sqrt{100} = 10$ . Hardware buys you a square root; a better algorithm buys you a different exponent.

Now you. A cubic algorithm takes 1.0 second on $n = 1000$ . How long does it take on $n = 5000$ ?

Answer

The input grew by a factor of 5, and cost grows as $n^{3}$ , so the work grows by $5^{3} = 125$ . The time is $125$ seconds, about two minutes. Going to $n = 10^{5}$ instead would be a factor of $100^{3} = 10^{6}$ , or about 11.6 days.

Combining bounds

Four rules cover almost every analysis you will do, and each follows from the definition in a line or two.

Sums take the maximum. If $f_{1} = O (g_{1})$ and $f_{2} = O (g_{2})$ then $f_{1} + f_{2} = O (\max (g_{1}, g_{2}))$ . Two loops one after the other, one linear and one quadratic, cost $O (n^{2})$ in total. This is why the dominant term is the only one written.

Products multiply. A loop running $n$ times whose body costs $O (n)$ costs $O (n^{2})$ . A loop running $n$ times whose body costs $O (\log n)$ costs $O (n \log n)$ , which is the shape of "sort by inserting each element into a balanced tree".

Constants disappear. $O (3 n) = O (n)$ , and $\log_{b} n = \log_{2} n / \log_{2} b$ , so the base of a logarithm is a constant factor and vanishes: $O (\log n)$ needs no base. Note that this is not true in an exponent, where $2^{n}$ and $3^{n}$ differ by ${1.5}^{n}$ , which is not a constant.

Nested loops are not automatically $n^{2}$ . A loop where the inner bound depends on the outer index needs the sum evaluated. The nested duplicate check of the previous lesson runs its inner loop $n - 1 - i$ times, summing to $n (n - 1) / 2 = Θ (n^{2})$ , whereas a loop that halves a counter each pass runs $Θ (\log n)$ times regardless of the outer loop.

Example. A function loops $i$ from 1 to $n$ , and for each $i$ it loops $j$ from 1 to $i$ , doing constant work in the body. Then it makes one pass over the array doing constant work. What is the total cost, tightly?

The double loop performs $\sum_{i = 1}^{n} i = n (n + 1) / 2$ constant-cost iterations, which is $Θ (n^{2})$ . The single pass is $Θ (n)$ . By the sum rule the total is $Θ (\max (n^{2}, n)) = Θ (n^{2})$ , and the $Θ$ is justified because the double loop is bounded both above and below by multiples of $n^{2}$ : $n (n + 1) / 2 \geq n^{2} / 2$ and $\leq n^{2}$ .

Now you. A function loops $i$ from 1 to $n$ , and for each $i$ it repeatedly halves a counter starting at $n$ until it reaches 1, doing constant work each halving. What is the cost?

Answer

The inner loop runs $⌊ \log_{2} n ⌋ + 1$ times, which is $Θ (\log n)$ and does not depend on $i$ . By the product rule the total is $Θ (n \log n)$ . The common mistake is to call it $Θ (n^{2})$ because two loops are nested; what matters is how many times each runs, not how deeply they sit.

Four ways this misleads

The notation is a tool for discarding information, and it is worth being explicit about what gets discarded, because every one of these has cost somebody a week.

Constants matter at real sizes. Suppose insertion sort costs $n^{2} / 4$ steps and mergesort costs $8 n \log_{2} n$ , which are plausible ratios once the recursion, the allocation and the copying in mergesort are counted. Setting them equal gives $n = 32 \log_{2} n$ , solved by $n = 256$ . Below 256 elements the "worse" algorithm wins, and at $n = 50$ it wins by a factor of 3.6. This is not a curiosity: real sort implementations switch to insertion sort on small blocks for exactly this reason, and Timsort, the sort in Python and in Java's Arrays.sort for objects, chooses a minimum run length between 32 and 64 and insertion-sorts anything shorter.

$O$ is an upper bound, and people read it as tight. "Quicksort is $O (n^{2})$ " and "quicksort is $O (n \log n)$ on average" are both true statements about the same algorithm, and a reader who does not notice which bound is being quoted will draw the wrong conclusion. Worse is the common phrase "at least $O (n)$ ", which is meaningless: $O$ is already an upper bound, so "at least an upper bound" says nothing. The word wanted there is $Ω$ .

Asymptotic means eventually, and eventually can be absurd. Strassen's 1969 matrix multiplication algorithm costs $Θ (n^{\log_{2} 7}) = Θ (n^{2.807})$ against the naive $Θ (n^{3})$ , and it does win on real hardware, with measured crossovers in tuned implementations somewhere from a few dozen to a few hundred. The descendants of Coppersmith and Winograd's method go much further, down to an exponent of about 2.372 in the current record, and none of them beats anything at any size a computer will ever be given, because their constants are astronomical. Such results are called galactic algorithms, and they are genuine mathematics with no engineering content.

Steps are not the only resource. The count says nothing about memory, and mergesort's extra array is the reason quicksort survives. It says nothing about cache behaviour, and a $Θ (n)$ walk over a linked list scattered through memory can lose to a $Θ (n \log n)$ pass over a contiguous array. It says nothing about the cost of the operations themselves, and every claim so far has quietly assumed that comparing two elements and reading a[i] cost the same fixed amount.

That last assumption is the one to attack next. Whether reading an element costs a constant depends entirely on how the elements are arranged in memory, and the two arrangements available, one block or a chain of separately allocated cells, give completely different cost tables for exactly the same operations. The next lesson starts with the block.