Counting the steps

Eight numbers sit on a page: 3, 9, 4, 7, 1, 8, 6, 2. To find the largest, read each number once and keep the best so far. That costs seven comparisons, one for each number after the first, because the first number starts as the best. Each comparison may also replace the best, so the job costs seven comparisons and at most seven replacements, which is fourteen small operations in the worst case. The worst case is the largest count over every possible list of that length, not the count for the list in front of you.

To find the two closest values, compare every number with every other. Each of the eight numbers meets the seven others, which is fifty-six ordered meetings, and each pair is met twice, once from each side, so the job has twenty-eight pairs. At eight items the second job is only twice the first, but the factor grows quickly with the length of the list. !One pass over eight numbers. Each comparison keeps the larger value, and only 9 replaces the running best, so this list costs seven comparisons and one replacement, eight steps. A list that keeps improving pays seven replacements, fourteen steps. Status: schematic.

At a thousand items the gap stops looking like a factor of two, because one pass costs 1,998 operations, one comparison for each item after the first and at most one replacement for each. The all-pairs scan costs 499,500, because it compares each item with every other item and counts every pair twice. The same job can therefore take a second in one program and a week in another, and the difference is not the machine but how many elementary steps each program performs as the input grows. !Two procedures on the same list. The one-pass count is about 2n, the all-pairs count about n squared over two. At eight items they differ by a factor of two, at sixteen by four, at a thousand by 250. Status: re-simulated.

Call one addition, one comparison or one assignment a step. Counting steps replaces counting seconds, because the number of instructions a processor executes during a run is difficult to predict exactly even for short code [S:11:24]. An algorithm is a finite, precise procedure that solves every problem in one class. Its time complexity is the number of steps it performs, written as a function of the size of its input. The size is whatever you choose to count: the items in a list, the digits in a number, or the rows in a table.

A class is a family of questions that differ only in their input, such as "find the largest number in this list" asked of lists of any length. Choosing a step is a modelling decision rather than a law of nature, since a machine that adds two small integers in one cycle and a machine that needs four cycles both perform one addition. What the count keeps is the shape of the growth: the rule that says how the count responds when the input gets larger.

A count of this kind is how Structure and Interpretation of Computer Programs introduces order of growth. The book, built on the Lisp language, defines order of growth as the amount of a resource a process requires for a problem of size n [S:13:83]. That resource can be time, counted in steps, or memory, counted in cells, and one definition covers both. The seconds a real computer takes are then proportional to the number of elementary machine operations it performs [S:13:83].

Worked example. Take the eight numbers above and count two procedures exactly.

The one-pass procedure compares each new item with the best so far and replaces the best when the new item wins. Its comparison count is n − 1, and its replacement count is at most n − 1, so its total is at most 2(n − 1) steps. The all-pairs procedure compares each item with every other item: there are n choices for the first item and n − 1 for the second, and dividing by two removes the double counting, which gives n(n − 1)/2 comparisons. At n = 16 the first needs 30 steps and the second needs 120, a factor of four, and at n = 1,000 the same comparison gives a factor of about 250.

Trace the one-pass procedure on the eight numbers in order. It starts with 3, then 9 beats it and replaces it, and then no later number beats 9, so the run performs seven comparisons and one replacement, which is eight steps. The table reports seven replacements because it reports the worst case, and the gap between one and seven is the difference between a report about one list and a promise about every list.

$$C(n)=2(n-1)$$

The one-pass cost is at most twice the number of items, minus two, and the subtraction matters only when the list is short. The words at most make it an upper bound: a ceiling that no list of length n can exceed, and that some list of length n reaches. It is not an exact count for every list, because the procedure replaces the best only when a new item is larger than everything before it.

The useful question is not how long the program took on your laptop but how the count changes when n changes. Double the list and the one-pass procedure does about twice the work, while the all-pairs procedure does about four times the work, and that difference in response is what the rest of this chapter measures, compares and predicts.

The count has a real cost of its own, because it treats every step as equal. It cannot see that reading a number from memory is slower than adding two numbers that already sit in a register, the small slot inside the processor that holds a value being worked on. Nor can it see that one machine multiplies in a single cycle while another needs several.

Two programs with the same count can differ by a large constant factor, meaning a multiplier that does not change as the input grows, and the count will not tell you which is faster. The model also assumes that a step costs the same wherever it sits in the program, which fails when the step waits for data to travel between memory and processor, the traffic that the count treats as free. Constants, memory traffic and the particular data you hold all sit outside the model, and the next section says what the standard notation does with them.

The formal statement. The core counted one addition, one comparison or one assignment as a step. The formal version fixes the machine that performs them. Work in the $w$-bit word-RAM: memory is a set of cells, each cell holds a $w$-bit integer, and basic operations on words take constant time [S:11:30]. The word size must satisfy $w\ge {\log }_{2}n$, so that one word can hold an index into the input [S:11:31]. A procedure costs the number of steps it performs, and the cost function $C(n)$ is the largest count over all inputs of size $n$.

The derivation. The core wrote $C(n)=2(n-1)$ and called it an upper bound. Under the definition above it is exact for the worst case, and the proof takes one line. The scan makes $n-1$ comparisons, one per item after the first. It replaces the running best exactly when the new item is larger than every item before it, and the increasing list achieves that at every position. So the maximum is $(n-1)+(n-1)$. A particular list can cost less: the eight numbers in the core make eight steps, not fourteen, because only one replacement fires. The core called the value an upper bound because it did not fix the input. Over all inputs of size $n$ the bound is attained, and over one list it may not be.

The edge case. Arithmetic on long integers breaks the picture. The model charges one step for adding two words, whatever the words represent. If the input is a single integer written in $n$ bits, it occupies about $n/w$ words, and adding two such integers costs about $n/w$ steps. A procedure that is linear in the number of items is then quadratic in the number of bits when each item is a long integer. The count is a statement about words, not about mathematical integers.

A second edge. The definition takes the maximum over inputs. You can average instead, but an average needs a probability distribution over inputs, and the worst case needs none. For the scan in this section, an increasing list attains the maximum, while a list that starts with its largest item performs no replacement at all. Neither number is wrong; they answer different questions.

Why the model survives. A program that runs in $T(n)$ steps on a word-RAM is simulated by a single-tape Turing machine in $O(T(n{)}^4)$ steps [S:1:402]. The exponent is large and nobody predicts a runtime from it. A polynomial stays a polynomial, though, and that is the only property sections 5.2 and 5.6 use.

What the core hid. Two things: the fixed word size and the dependence of a step's cost on operand width. The core named the worst case and called the choice of step a modelling decision, so it hid neither of those. It could leave the machine unnamed because it compared growth shapes, and both omissions change only a constant or a lower-order term.

Original sources. The idea that a process consumes a resource you can count as a function of problem size is SICP's order of growth. The book writes $R(n)$ for the amount of a resource a process requires for a problem of size $n$ [S:13:83]. The machine model that makes the count precise is the word-RAM, with one word per cell and constant-time operations on words [S:11:30]. Erickson states the same model in his formal definitions, with unit time per instruction [S:1:402]. The step is a convention, and these sources fix it.

An open question. The field has not settled how to build a cost model that is simple enough to reason about and accurate enough to rank two programs on one machine. A single step count ignores memory traffic, and the roofline work argues that off-chip memory bandwidth will often be the constraining resource [S:104:3]. Evidence that would settle it: a model with a few parameters that predicts the crossover between two implementations across machines, fitted on one benchmark and tested on another without per-program tuning.

A frontier result. The roofline model replaces the step count with two ceilings, peak floating-point performance and peak memory bandwidth times operational intensity, and takes the smaller [S:104:4]. The move is the same as in 5.1: replace a stopwatch with a count of a resource. The resource is now bytes moved rather than operations performed, and the prediction is a bound rather than a number. A step count answers how the work grows; a roofline answers which ceiling you hit first.

What to read next. Read section 1.4 of Open Data Structures for the word-RAM and the $w\ge \log n$ assumption [S:11:31]. Read the formal definition in Erickson for the comparison with a Turing machine [S:1:402]. Then read the roofline paper to see what a step count leaves out [S:104:4].