Counting Steps, Not Seconds

A stopwatch measures one machine on one input. Counting the operations a piece of work performs measures the work itself, and that number is the one that predicts next year.

Two procedures are measured on the same thousand rows. One takes 40

milliseconds and the other 90. Which should be used on a million rows?

Nothing in those two numbers answers that. The slower one may be four times

slower at every size, or it may be the only one of the two still running

tomorrow.

FIG 1The same two procedures, measured and counted

	ms on a laptop, 1000 row	ms on a server, 1000 row	ms on a laptop, 100000 r	operations, as a count
procedure A, scanning on	90	30	9000	1
procedure B, comparing e	40	13	400000	2

The two marked cells are the same procedure at two input sizes, and they are the whole lesson. At a thousand rows B wins comfortably, and at a hundred thousand it has lost by a factor of forty four, because the work it does grows with the square of the input while A grows in proportion. The server column shows the other reason timings do not travel: every number shrinks by roughly a factor of three, which changes nothing about which procedure is the right choice. The last column, written here as a code rather than a measurement, is the only one that is a property of the procedures themselves.

Naming the size

Before anything can be counted, it has to be counted against something. Call

it $n$ , and say what it is: the number of rows, the length of the list, the

count of nodes.

The choice is usually obvious and occasionally not. A procedure on a graph has

two sizes, the nodes and the edges, and its cost generally depends on both. An

image has a width and a height, and a procedure that visits every pixel is

linear in their product and quadratic in the side length, which are the same

statement about the same code.

The trap is a number given as input. A loop that counts up to a number $N$

runs $N$ times, which sounds linear and is not: the input is the number

itself, written in about $\log_{10} N$ digits, so the loop runs exponentially

many times in the size of what was actually supplied. That distinction is

behind a surprising amount of confusion, and naming the size out loud avoids

all of it.

FIG 2Counting the comparisons in a scan for the largest value

step	stage	what happens	comparisons so far
1	setup	take the first item as the current best	0
2	second item	compare it with the current best	1
3	third item	compare it with the current best	2
4	fourth item	compare it with the current best	3
5	the nth item	compare it with the current best	n - 1
6	finished	return the current best	n - 1 in total

6 steps

The count is exact rather than approximate: every item after the first is compared once, so the total is one fewer than the number of items. Notice what was left out. Loading the list, setting up the variable and returning the answer each happen once regardless of size, and at a million items those few operations are invisible beside the million comparisons. Leaving them out is not sloppiness; it is the step that makes the count short enough to reason with, and the next lessons make the practice precise.

FIG 3The cost written as a function

: the count of operations performed on an input of size n
: the input size, named explicitly before any counting began
: the operations done per item in the scanning procedure
: the operations done per pair in the comparing procedure
: the fixed setup cost, the same for both and soon irrelevant

Both expressions are worth writing down rather than describing, because once written they can be evaluated. Put in a thousand and the second is about five hundred times the first; put in a million and it is about five hundred thousand times. The constants differ between the two procedures and between machines, and none of that changes the comparison once n is large, which is the observation the next two lessons build the whole method on. Note that the second expression counts pairs, which is where the n squared shape comes from before any constant is attached.

FIG 4The two procedures, with their counts next to them

python

def largest(xs):
    best, steps = xs[0], 0
    for x in xs[1:]:
        steps += 1                      # one comparison per item after the first
        if x > best:
            best = x
    return best, steps

def closest_pair_gap(xs):
    gap, steps = float('inf'), 0
    for i in range(len(xs)):
        for j in range(i + 1, len(xs)):
            steps += 1                  # one comparison per pair
            gap = min(gap, abs(xs[i] - xs[j]))
    return gap, steps

xs = list(range(1_000))
print(largest(xs)[1], closest_pair_gap(xs)[1])   # 999 and 499500

Each function carries a counter so the analysis can be checked rather than believed. The first performs one comparison per item after the first. The second performs one per pair, which is the number of ways to choose two items from the list. Running both at a thousand items prints 999 against 499500, a ratio of about five hundred, and running at ten thousand prints a ratio of about five thousand. That agreement between the predicted count and the observed count is the check worth doing on any analysis.

What the count is for

It is not a prediction of seconds, and it should not be used as one. It is a

prediction of how the seconds change when the input changes, which is a

different and more durable thing.

That is enough to answer the question this lesson opened with. Procedure B is

the right choice at a thousand rows and the wrong one at a million, and the

count says so without anybody running it at a million.

What comes next

There is a small number of growth shapes that nearly all real work falls into,

and knowing them in order is most of the value of this subject. That is the

next lesson.

Recap

A timing measures the machine, the input and the code together, so it answers a question about today. Counting operations as a function of the input size answers the question about tomorrow.
The count is written as a function of one number, the size of the input, which has to be chosen and named before anything can be counted. Different choices of size give different and equally correct answers.
Only the operations that grow with the input matter. The rest form a fixed cost that becomes invisible as the input grows, which is what makes the count short enough to be useful.

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

NextThe Shape of the Curve →