Measuring growth on a real machine

Double the input, watch what the time does, and read the exponent straight off the ratio.

An analysis is a prediction, and a prediction can be checked. Running the program at several sizes and watching how the time responds catches two things nothing else does: an error in the counting, and a constant factor so large that the theoretically better procedure loses on every input you actually have.

The experiment that reveals the most is the simplest one available. Run the same procedure on an input, then on an input twice as large, then twice as large again, and look at the ratio between consecutive times rather than at the times themselves. The first pass is a warm-up whose time is thrown away, because a machine that has been idle takes a moment to come up to speed and would make the smallest size look artificially slow.

The times depend on the machine, the day and what else is running. The ratios do not: each doubling of the input multiplies the time by roughly 4. That number is the measurement worth writing down, because it names the growth.

Turning a ratio into an exponent

Suppose the running time behaves like $T(n) = c\,n^b$ for some constant $c$ and some power $b$. Then doubling the input gives $T(2n) = c\,(2n)^b = c\,2^b n^b$, so the ratio is $T(2n)/T(n) = 2^b$. The unknown constant $c$ cancels, which is why the ratio survives a change of machine.

Here is the arithmetic on one measured pair, with every step. Suppose $T(1000) = 0.0410$ seconds and $T(2000) = 0.1652$ seconds. The ratio is $0.1652 / 0.0410 = 4.03$. Now $\log_2 4.03$ is the power of 2 that gives 4.03, and since $2^2 = 4$, that power is a little above 2, in fact 2.01. So $b \approx 2$ and the measured growth is quadratic.

Not every growth is a power of $n$, and the method still tells you something when it is not. The next snippet takes three sets of measurements already recorded, so the numbers are the same every time you run it, and reports the exponent implied by each doubling.

Machine A's ratios are 2, so its exponent is 1 and the growth is linear. Machine C's are 4, so its exponent is 2 and the growth is quadratic. Machine B sits at about 2.18, giving an exponent near 1.13, which is not a whole number and is not meant to be: a cost of $n\log_2 n$ has ratio $2(\log_2 n + 1)/\log_2 n$, a value that starts above 2 and drifts slowly down towards it as $n$ grows.

What the model charges nothing for

The RAM model says every memory cell costs the same to reach as every other. That is false on real hardware, and the falsehood does not change the growth. What it changes is the constant, and the constant is what you feel.

The next snippet walks an array of about four million cells and adds up what it finds, twice over. Both walks read four million cells, perform four million additions and finish on the same total. The only difference is the stride, meaning the gap between one position visited and the next: the first walk uses a stride of 1 and steps to the neighbouring cell, the second uses a stride of 4099 and lands a long way off each time.

The remainder operation % n sends a position that has run off the end back round to the start, so both walks stay inside the array and both visit every cell exactly once, in a different order. Predict which one finishes first before you run it.

The two walks perform the same number of arithmetic operations and the jumping one takes longer, commonly two or three times longer. The reason is that a machine fetches memory in blocks of neighbouring cells and keeps the blocks it touched recently in a small fast store called a cache. Stepping to the next cell usually finds it there already; jumping 4099 cells usually does not, and the walk waits for main memory.

That gap is invisible to the analysis and decisive in a real program, which is why measurement is a companion to analysis rather than a replacement for it: the analysis tells you which algorithm survives a bigger input, the measurement tells you which implementation to ship today.