Counting steps instead of timing

Why do computer scientists count imaginary steps rather than simply timing the program?

Timing a program is easy, exact, and requires no theory. Counting hypothetical steps on a machine nobody owns, then throwing away the constants and every term but the largest, sounds like a worse version of the same thing.

So the question is open: what does the abstract count give you that the stopwatch does not, and what does it cost in exchange? Both halves matter, because the answer is not that counting is better — the two answer different questions, and confusing them causes trouble in both directions.

Begin with what a timing actually is. You ran this implementation, this compiler, this processor and cache, these inputs, with whatever else the machine was doing. Change any of them and the number changes. It is a measurement of an event, not a property of the algorithm.

Which is fine if you wanted to know how long this run took. But the question that usually motivates the analysis is different: if the input grows tenfold, does the cost grow tenfold, a hundredfold, or beyond any tolerance? That is a question about a family of runs, most of which you cannot perform — and extrapolating from the sizes you could afford to measure is exactly where prediction is least reliable.

So we want something invariant. Fix an abstract machine instead — conventionally the random-access machine, where arithmetic and comparison on a word cost one unit and any memory location can be read in constant time — and count operations as a function of input size n. The answer is now a formula rather than a measurement, and it is the same on every processor.

Then the step that looks arbitrary and is not: why discard the constant factor?

Ask what the constant actually represents. It absorbs the clock speed, the instruction set, the compiler's choices, and — crucially — your own arbitrary decision about what counts as one step. Count comparisons and you get one constant; count machine instructions and you get another; the algorithm has not changed. So a measure that keeps the constant is not even well defined until the cost model is pinned down to a degree that would destroy its portability. Discarding it is not convenience: it is the precise act of quotienting out everything that varies with the machine and the accounting convention, leaving what belongs to the algorithm.

Lower-order terms go for a related but distinct reason. In n squared over two plus three n plus seven, the ratio of the smaller terms to the largest tends to zero as n grows. They may well dominate at n equal to five, but the question being asked is about growth, and in the limit they contribute nothing to it.

Now hold that result up honestly, because the same reasoning says what it cannot do. Having thrown the constant away, the analysis cannot predict a running time, cannot rank two algorithms in the same class, and says nothing about the regime where n is small enough for the constant to dominate. These are not edge cases. Production sorting routines fall back to insertion sort below a few dozen elements because its quadratic growth has not yet caught up with its tiny constant. Matrix multiplication algorithms with better exponents go unused because their constants are astronomical — they are called galactic algorithms for precisely that reason. Fibonacci heaps improve on the amortised bounds of binary heaps and are frequently slower in practice.

The abstract machine's own assumption deserves scrutiny too. Constant-time access to any memory location is false on real hardware, where a cache miss costs orders of magnitude more than a hit, so two algorithms of identical asymptotic cost can differ severalfold through locality alone. That is why external-memory and cache-oblivious models exist: the cost model is a modelling decision, not a fact.

Which leaves the relationship clear. Counting steps rejects designs that cannot survive growth, and it does so before anything is built and without access to a machine. Timing chooses among the survivors on the hardware you actually have. Neither substitutes for the other, and reaching for one where the other is needed is the recurring error.

Three refinements.

First, the notation is more precise than casual use suggests. Big O is an upper bound — an algorithm that is Theta of n is also O of n squared, truthfully but uselessly. Big Theta is a tight bound, both above and below, and is usually what people mean when they say O. Big Omega is the lower bound.

Second, a complexity claim is incomplete without saying over which case. Quicksort is Theta of n squared in the worst case and Theta of n log n on average; a dynamic array's push is linear in the worst case and constant amortised over any sequence. Dropping the qualifier is how a correct bound becomes a misleading one.

Third, growth class and speed are independent enough that both should be checked. A design review that looks only at the class ships something correct and slow; one that looks only at the stopwatch ships something fast that falls over at ten times the volume.

• When the random-access model's constant-time memory assumption breaks badly enough to need a cache-aware model instead.
• How amortised analysis justifies a bound over a sequence of operations that no single operation meets.
• Why some problems have proven lower bounds, so no future algorithm can beat a certain growth rate.

Every term the collection defines is gathered in the glossary.