Counting Steps, Not Seconds

A stopwatch tells you how long one run took, on one machine, with one input, on one afternoon. It says almost nothing about the next run, and nothing at all about the run on ten times the data. Counting steps as a function of the input's size tells you how the cost grows, and growth is the only thing that transfers from the test environment to production.

This topic sets the cost model the whole book uses. Pick the input that grows, call its size n, and count the basic steps the procedure takes as n changes. The model is deliberately crude. It does not predict nanoseconds. It ranks procedures, and it predicts what happens when n gets bigger, which is the question every capacity plan is really asking.

Why the Stopwatch Lies

A timing mixes the procedure with everything around it: the machine, the other processes sharing it, whether the data was already in the processor's cache or the operating system's memory, the interpreter version, and the particular input. Time the same function twice on the same laptop and the results can differ by tens of percent. Time it on 1,000 records and it tells you nothing reliable about 2 million.

None of this makes timing useless. It makes timing an answer to a narrow question: how slow is this code, here, now. The question engineers need answered before shipping is a different one. How slow will it be when the input is a hundred times larger?

The Input Size n

Cost is always a function of something that grows. For a search it is the number of records. For a parser it is the number of characters. For a route planner it is the number of stops. Choosing n is the first decision in any analysis, and getting it wrong makes everything after it wrong.

Some operations need two sizes. A Lantern search depends on the size of the catalogue and on the length of the lists of matching records it has to read, and those grow differently. A popular word such as "history" matches hundreds of thousands of records; a rare surname matches three. A useful cost for that search names both numbers.

What Counts as One Step

The model counts operations whose cost does not depend on n: comparing two numbers, adding them, reading or writing one element of a list by its position, and, on average, one dictionary lookup. Each counts as one step. They do not really take the same time, and the model does not pretend they do. It only needs them to be bounded, so that counting them tells you how the total grows.

That crudeness is the point. A model precise enough to predict nanoseconds would have to describe the processor, the cache and the interpreter, and would be wrong on the next machine. A model that counts bounded steps is right on every machine about the one thing that matters most: how the work changes when the data does.

The Steps Hidden in One Line

Most accidental slowness hides inside a line that looks like one step. Testing whether a value is in a list reads the list until it finds it. Inserting at the front of a list shifts every element one place along. Taking a slice copies it. Sorting costs about n times log n comparisons. Adding two strings builds a new string and copies both.

for record in new_records:           # n times
    if record.id in seen_list:      # reads up to n items: n × n steps
        continue

for record in new_records:           # n times
    if record.id in seen_set:       # one hash lookup on average: n steps
        continue

The two loops above skip records already seen. They differ in one word. In the first, the membership test reads through a list, so for each of n records it may read n entries, and the whole loop costs on the order of n times n steps. In the second, the test is a hash lookup that takes one step on average, so the loop costs n. On the 3.15 interpreter, a thousand membership tests against a list of ten thousand numbers took about a thousand times longer than the same tests against a set. Nothing on the line says so.

Counting Lantern's Two Searches

Scanning the catalogue checks each of the 2 million records, so its step count is proportional to n, the catalogue size. Looking a term up in the index finds the term in a bounded number of steps and then reads that term's list of matching records. Its cost is proportional to the number of matches, not to the size of the catalogue.

For a typical query, whose terms match hundreds or thousands of records, the two counts still differ by a factor of hundreds to thousands before any machine is involved. That difference exists on paper, in the procedures themselves, and no benchmark is needed to see it.

The Price of Growth

A test suite with 1,000 records hides the difference between procedures, because at that size everything is fast. At 2 million records, a procedure whose steps grow in proportion to n does 2,000 times the work. A procedure whose steps grow with n times n does 4 million times the work. A test that took 2 milliseconds becomes 4 seconds in the first case and a little over two hours in the second.

Only the step count predicts which of those two the release contains. The cheapest way to see it without a model is to time the code at two sizes, ten times apart, and compare the ratio. If ten times the input costs about ten times the time, the work is linear. If it costs a hundred times, it is quadratic, and it will be visible in the ratio long before it hurts in absolute terms.