Counting the cost

A program that returns the right answer can still be worthless, and nothing in an introductory programming course gives you a way to say so.

Two correct programs

Here is a task with no ambiguity in it. Given a list of $n$ numbers, say whether any value appears twice. Both of the following solve it, and both are correct in the sense that they return the right answer on every input.

The first compares every element with every later element. For a list of six numbers that is five comparisons involving the first element, four more involving the second, and so on down to one, which is fifteen comparisons in total. In general it is $n (n - 1) / 2$ : for a hundred numbers, 4950 comparisons; for a million, 499,999,500,000.

The second sorts the list first and then walks it once, checking each element against its neighbour. Sorting a million numbers well takes roughly $n \log_{2} n$ comparisons, about 19.9 million, and the walk adds a million more. Call it 21 million against 500 billion.

If the machine performs a billion comparisons a second, and both programs are otherwise identical in every respect, the first finishes in about eight minutes and the second in about a fiftieth of a second. The ratio at a million items is roughly 25,000. Push the input to a hundred million and the ratio passes 1.8 million: two and a half seconds against nearly two months.

Nothing in the previous course could distinguish those two programs. Correctness is a property they share. The difference between them is a property nobody has yet named, and this lesson names it: cost, meaning how the resources a program consumes grow as its input grows. The whole subject is the study of that quantity, because it is the only property of a program, apart from correctness, that survives being ported to a different machine.

The stopwatch measures the machine

The obvious way to measure cost is to run the program and time it. This is a real measurement and it is worth doing, but on its own it answers the wrong question.

Suppose you time the nested-loop version on a laptop and it takes 5.0 seconds on 100,000 numbers. What have you learned? That number depends on the processor's clock speed, on how much of the array fitted in cache, on whether the language was compiled or interpreted, on whether a browser was updating in the background, and on how many times the just-in-time compiler had already seen that loop. Move to a machine twice as fast and it becomes 2.5 seconds. Rewrite the same algorithm in C and it might become 0.8 seconds. None of those changes tell you anything about the algorithm, because the algorithm never changed.

Worse, the stopwatch answers only for the input you happened to try. Timing at $n = 100 {,} 000$ does not tell you what happens at $n = 10^{7}$ , and the whole reason to care is that inputs grow. A measurement that has to be repeated for every size and every machine is not a theory, it is a table.

What is wanted is a number attached to the algorithm rather than to the run: a count of the operations the algorithm performs, expressed as a function of the size of its input. Two things follow immediately. First, "operation" has to be pinned down, since the count is meaningless until you say what you are counting. Second, the count has to be a function of a single number $n$ , which means deciding what "size" means.

A model of a machine

The standard idealisation is the RAM model, short for random access machine, and it is the model every complexity claim in this course is made against. It says: the machine has an unbounded array of memory cells, each holding one value; reading or writing any cell costs one step regardless of its address; and a fixed set of primitive operations on those values, arithmetic, comparison, assignment, and the jumps that implement control flow, each cost one step.

Under that model, counting is mechanical. A single assignment is one step. A loop body of $k$ steps run $m$ times is $k m$ steps. Indexing a[i] is one step, whether i is 0 or 999,999.

The model is a lie in three specific places, and knowing where it lies is what stops you trusting it too far. It says all memory access costs the same, but real machines have caches, and a read that hits the fastest cache can be a hundred times quicker than one that goes to main memory. It says arithmetic on a value costs one step, which is true for machine-word integers and false for the thousand-digit numbers used in cryptography, where multiplication has its own cost function. And it counts steps rather than joules or bytes, so a program that is fast and needs an extra copy of the input looks free.

Nevertheless it is the right default. It is machine-independent, it is simple enough to count in, and its predictions about which of two algorithms wins at large $n$ are almost always right. Where it fails, later lessons say so explicitly: the memory hierarchy is exactly why B-trees exist, and space is exactly the price mergesort pays.

Counting steps against input size

Size means the number of things in the input: the length of the array, the number of vertices in a graph, the number of characters in a string. It is written $n$ , and where two quantities matter independently, as with a graph's $V$ vertices and $E$ edges, both are named.

Take the nested-loop duplicate check and count it exactly. The outer loop runs with $i$ from $0$ to $n - 2$ . For each $i$ , the inner loop runs with $j$ from $i + 1$ to $n - 1$ , so it performs $n - 1 - i$ comparisons. The total is

\sum_{i = 0}^{n - 2} (n - 1 - i) = (n - 1) + (n - 2) + \dots + 1 = \frac{n (n - 1)}{2}

If each pass of the inner loop costs a comparison, an increment and a bounds test, three steps, the program costs about $3 n (n - 1) / 2$ steps plus a fixed amount of setup. Written out, $1.5 n^{2} - 1.5 n + c$ .

Example. How many comparisons does the nested-loop duplicate check perform on a list of 100 numbers, and on a list of 1000?

Substitute into $n (n - 1) / 2$ . For $n = 100$ that is $100 \times 99 / 2 = 4950$ . For $n = 1000$ it is $1000 \times 999 / 2 = 499 {,} 500$ . The input grew by a factor of 10 and the work grew by a factor of about 101, which is the quadratic behaviour showing itself: the ratio approaches $10^{2}$ from above because of the $- n$ term.

Now you. How many comparisons does it perform on a list of 500 numbers? By what factor does that exceed the count for 100?

Answer

$500 \times 499 / 2 = 124 {,} 750$ comparisons. Against 4950 for $n = 100$ , the ratio is $124 {,} 750 / 4950 = 25.2$ , close to the $5^{2} = 25$ that a purely quadratic cost would give.

Three questions, not one

An exact count of $n (n - 1) / 2$ is unusually tidy, because that algorithm does the same work on every input of a given size. Most do not. Linear search, scanning an array from the front until the target is found, is the standard illustration.

If the target sits in the first cell, the search costs one comparison. If it sits in the last, or is absent, it costs $n$ . So "the cost of linear search on $n$ elements" is not a single number, and pretending otherwise is how people end up surprised. There are three separate questions, and they have three separate answers.

The best case is the smallest cost over all inputs of size $n$ : one comparison. It is nearly useless for prediction, because it describes the luckiest input rather than a typical one, and any algorithm can be made to look good on a case chosen for it.

The worst case is the largest cost over all inputs of size $n$ : $n$ comparisons. It is the default in this course and in most of the literature, for two reasons. It is a guarantee, which is what you need when the program controls an aircraft or a trading system, and it is a claim about all inputs, so it needs no assumption about which inputs occur.

The average case is the expected cost over some distribution of inputs, and the phrase hides the important part: which distribution. Suppose the target is present and equally likely to be in any of the $n$ positions. The cost is $i$ comparisons when the target is at position $i$ , each with probability $1 / n$ , so the expected cost is

\frac{1}{n} \sum_{i = 1}^{n} i = \frac{1}{n} \cdot \frac{n (n + 1)}{2} = \frac{n + 1}{2}

about half the array. That number is only as good as the assumption. If the target is usually absent, every search costs $n$ . If the data are requests to a web cache, where a few keys are asked for constantly, the average is far below $n / 2$ and the uniform model is simply wrong. An average-case claim without a stated distribution is not a result.

Example. An array holds 1000 distinct values. Under the assumption that the searched-for value is present and equally likely to be at any position, what is the expected number of comparisons for linear search, and what is the worst case?

Expected cost is $(n + 1) / 2 = 1001 / 2 = 500.5$ comparisons. Worst case is $n = 1000$ , when the value is in the last cell. Note that the average is not half the worst case by coincidence: it is $(n + 1) / 2$ against $n$ , a ratio approaching $1 / 2$ as $n$ grows.

Now you. The same array, but now half of all searches are for values that are not in the array at all, and the other half are for values uniformly placed within it. What is the expected number of comparisons?

Answer

An absent value costs the full 1000 comparisons, since the scan must reach the end to be sure. So the expectation is $0.5 \times 1000 + 0.5 \times 500.5 = 500 + 250.25 = 750.25$ comparisons. Changing the input distribution, with no change at all to the algorithm, raised the average by half.

What "size" means, exactly

One trap deserves naming early, because it recurs in the last lesson of this course.

Consider testing whether an integer $N$ is prime by trying every divisor from 2 up to $\sqrt{N}$ . That is about $\sqrt{N}$ operations, which sounds cheap. For $N$ around $10^{18}$ it is $10^{9}$ divisions, a second or so.

But the input to that program is not $N$ things. It is the number $N$ , written down, which takes about $\log_{2} N$ bits: 60 bits for $10^{18}$ . So the input size is $b = 60$ , and the cost $\sqrt{N} = 2^{b / 2}$ is exponential in the size of the input. Adding two digits to $N$ multiplies the work by ten. At 200 digits, the numbers used in RSA, trial division would take longer than the age of the universe, and that is precisely why the method is safe to build a cryptosystem on.

The lesson is that $n$ counts symbols in the input, not the magnitude of a number in it. For arrays and graphs the two coincide and nobody thinks about it. For algorithms whose input is a number, they do not, and the distinction is exactly what separates a polynomial-time algorithm from an exponential one.

Example. How many divisions does trial division perform on $N = 10^{12}$ , and how many bits long is that input?

The divisor runs up to $\sqrt{N} = 10^{6}$ , so about a million divisions, which is instant. The input is $\log_{2} 10^{12} = 39.9$ bits, so 40 bits, and the cost $10^{6}$ is close to $2^{20} = 2^{b / 2}$ with $b = 40$ .

Now you. Repeat for $N = 10^{24}$ .

Answer

$\sqrt{N} = 10^{12}$ divisions, about seventeen minutes at a billion per second, and the input is $\log_{2} 10^{24} = 79.7$ bits, so 80. Doubling the length of the input squared the work, which is the signature of exponential cost in the input size even though $\sqrt{N}$ looks like a modest function of $N$ .

Why exact counts do not survive

So the duplicate check costs $1.5 n^{2} - 1.5 n + c$ steps. Now try to defend that expression to somebody with a different compiler.

The 1.5 came from a guess that a comparison, an increment and a bounds test cost one step each. On a real processor, the comparison and the test may fuse into one instruction, the increment may be free because it overlaps with a memory load, and the whole loop may be vectorised to handle four elements at once. The constant is not 1.5. It is not knowable without naming the machine, and once you name the machine you are back to timing.

The $- 1.5 n$ term is more solidly derived, since it comes from the arithmetic rather than the hardware. But look at what it contributes. At $n = 1000$ the quadratic term is 1,500,000 and the linear term subtracts 1500, one part in a thousand. At $n = 10^{6}$ it is one part in a million. Any term of lower degree is invisible at the sizes where cost actually matters.

What is left after discarding the indefensible constant and the invisible lower terms is the shape: this cost grows like $n^{2}$ . That single fact predicted the eight minutes against the fiftieth of a second at the start of this lesson, and it did so without knowing the machine. The next lesson makes "grows like" precise, with a definition that has explicit witnesses and can be proved rather than waved at, and then prices the resulting hierarchy of shapes in real seconds.