When counting steps misleads you

Three situations where the cost on paper is not the cost you get, and what to do about it.

Counting steps is the right way to understand a structure, and it is the tool this whole course is built on. It is also, taken alone, capable of steering you badly wrong. This lesson is the honest small print, and it will save you from a few confident wrong decisions.

One: your data may simply be small

All the reasoning about growth is about what happens as n gets large. If your collection holds thirty items and always will, the growth pattern is close to irrelevant. What matters at that size is the fixed costs that big O deliberately discards.

Scanning thirty items in a packed run is thirty cheap comparisons over data sitting right next to each other. A cleverer structure has to do arithmetic, follow pointers, and jump around memory before it can answer anything. The simple scan very often wins, and it is easier to read as well.

Two: not all steps cost the same

We have been treating a step as a step. Real machines disagree, and the reason is worth knowing because it explains results that otherwise look impossible.

Early in this section you were told that reaching any address costs the same whichever address you name. That is true in the sense that matters for counting steps: no address is harder to work out than any other, and none of them takes more steps to name. It is not true in seconds, and here is why.

Main memory is comparatively slow to reach, about eighty times slower than the fastest storage the processor has, so processors keep a small, very fast store of recently used data close by, called a cache. Memory is also never fetched one box at a time. When the processor needs one address, it pulls in a whole chunk of neighbouring memory around it, typically 64 bytes, which is 64 of the boxes from the memory lesson, on the reasonable assumption that you will want the neighbours soon.

That is worth turning into a number we can use. Our numbers are four boxes each, and a chunk is 64 boxes. 64 divided by 4 is 16, so one trip out to main memory brings back sixteen of our numbers: the one you asked for, plus fifteen neighbours.

So if your data is packed together, those sixteen arrive as a set. You pay for one trip and the next fifteen reads then cost almost nothing, because the data is already sitting in the fast store. If your data is scattered across memory, the fifteen neighbours that came along belong to somebody else, or to nothing at all, so every single item is a fresh trip.

already in cache      : about  1 unit of time
out in main memory    : about 80 units of time

100 packed steps  : 100 / 16 = about 7 trips out, so about 560 units
10 scattered steps: 10 trips out,                 so about 800 units

so: 100 steps over packed data can finish sooner
    than 10 steps over scattered data.

The scattered version does ten times fewer steps and still finishes last. The step count was not wrong. It was simply counting something other than what the machine charges you for.

Three: the mix of operations is what actually matters

A cost table shows each operation separately, which invites you to compare them one at a time. That is not the decision in front of you. The decision is about the mix.

Suppose a structure searches in one step but takes a thousand steps to insert, and your program does one insertion an hour and ten thousand searches a second. The thousand-step insertion is completely irrelevant. Work out what your program actually does, and how often, before comparing anything.

What to carry into the rest of the course

From here on, every structure gets the same treatment. What is the arrangement in memory. What rule does it keep. What do access, search, insert and delete cost, and why does the arrangement make them cost that. And what does it cost in space, over and above the data itself, since pointers and spare capacity are paid for in memory just as surely as shifting is paid for in time. You now have every idea needed to follow those answers, and more usefully, to work out most of them yourself before you read them.