Maths/Big O notation

The machine model

After thiswhat you will be able to doState what the random access machine model counts as one step, and identify when growing numbers or unequal memory access make that model stop matching a real machine.

Questionwhat this lesson answersThe whole arc counted steps and treated every step as costing the same, but never said what one step is. What is the model that makes "one step" well defined, and what does treating all steps as equal quietly assume that a real machine breaks?

Not coveredwhat this lesson leaves outWe describe the standard counting model and name two places it stops matching real hardware. We do not build the cost model of a real processor, and we do not measure anything.

The arc has counted loop iterations, comparisons, copies, and reads as though each one were one unit of the same size. It divided those units, added them, and compared their response to a larger input. That made the counting useful, but it also left a gap. A loop count tells us how often a line runs. It does not yet tell us what the line costs. Before a step count can be a number, we have to agree on what one step is.

Start with the agreement rather than its name. We decide that adding, subtracting, comparing two values, reading a numbered storage slot, and writing to one each take one fixed unit of time. A number is also limited to a fixed-size group of binary positions, called bits. That group is large enough to hold the values we expect to handle in one operation. We call the group a word. Finally, every numbered storage slot can be reached in the same one unit, whether it was used a moment ago or has not been touched at all.

That is the standard counting model. It is called the random access machine model because the location of a storage slot does not alter the charge for reaching it. Within this model, each of the agreed actions is a primitive step. The name comes after the agreement on purpose. A primitive step is not a fact discovered by measuring a processor. It is one action the model chooses to charge once. This is what makes the instruction “count the steps” meaningful. Without the choice, a step count has no unit and therefore no number to report.

The earlier lessons quietly relied on all three parts. When the cost lesson described an input of ${n}$ items, it treated each item as fitting in one word. When the loop lesson counted one run of an inner line, it treated the comparison and the counter update as a fixed amount of work. When the arc compared two costs, it treated a read from any storage slot as no more expensive than any other. Those are not small omissions. They are the floor under every total in the arc.

The first crack appears when a value no longer fits in a word. A calculator can display a very large integer as one value, but a machine must hold it across many word-sized pieces. Addition then has to visit those pieces and carry a change from one digit position into the next. Adding two values with more digit positions takes more primitive actions than adding two values with fewer digit positions. It is not one step in the same sense as adding two ordinary word-sized values.

This matters when the numbers inside a computation grow along with the input. If a program adds counts so large that they spill past one word, its arithmetic cost grows even if the code still contains one visible addition instruction. The word-sized assumption is therefore an approximation with a boundary: it works while every number used by the algorithm stays inside the fixed-size chunk we chose. It stops working when the data itself needs a growing amount of space. The unit-cost bar in the island makes that assumption. The second bar charges the same list sum by the number of decimal digit positions in its running total, so a changed model changes the count without changing the list-summing algorithm.

The second crack is storage. A real computer does not keep all its memory at one distance from the part that carries out instructions, called the processor. It keeps a small amount of very fast storage close to that part, and much more storage farther away. The arrangement is called a memory hierarchy. Its fast layers are called caches. A value already in a cache can be read far more cheaply than a value that must travel from a slower layer. When the requested value is not in the fast layer, that event is called a cache miss.

The model’s claim that any storage slot costs one unit is a useful fiction. It is more accurate for an access pattern that reuses nearby values than for one that jumps around a large region of memory. This is also why a discarded constant can vary between machines. Two computers can run the same sequence of primitive steps while one finds more of its needed values in a cache. The When the constants come back door examined the practical result: equal growth classes do not make equal running times on a finite machine.

The payload is not that step counts are false. A model is a choice, not a fact about hardware. The random access machine model was chosen because it makes counting possible and because it predicts growth well enough for word-sized data with cache-friendly access, meaning access that reuses nearby stored values. It makes a sharp question possible: how does the arrangement of the work respond when the input grows?

The “one step” that bottomed out in What we agree to throw away bottoms out here because we have decided where the model starts. Change that decision and the count can change. A model that charges per binary position gives a different total for oversized arithmetic. A model that charges for a cache miss gives a different total for memory access. Sometimes the new total has the same growth shape with a different multiplier. Sometimes it has a different shape altogether. The doors reopen those choices rather than pretending that one count is the only count an algorithm can have.

The arc’s step counts are true statements inside this model. They stop being the whole truth at the exact places where the model stops matching the machine: when values no longer fit in a word, or when reaching storage is no longer uniform. Stating the model makes that boundary visible. It does not make the boundary go away.