How do you compare two algorithms before you time either? Count their steps. Watch one loop make a line and a loop inside a loop make a curve.
Counting an algorithm's steps
A loop and a loop over pairs, on arrays of 1 to 8 numbers
static long steps = 0; int sum(const int *a, int n){ int total = 0; for (int i = 0; i < n; i++) { total = total + a[i]; steps++; } return total;} int count_equal_pairs(const int *a, int n){ int pairs = 0; for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) { if (a[i] == a[j]) pairs++; steps++; } return pairs;} int main(void){ int a[8] = { 3, 1, 4, 1, 5, 9, 2, 6 }; for (int n = 1; n <= 8; n++) { steps = 0; int t = sum(a, n); printf("n = %d: sum %d in %ld steps\n", n, t, steps); } for (int n = 1; n <= 8; n++) { steps = 0; int p = count_equal_pairs(a, n); printf("n = %d: %d equal pairs in %ld steps\n", n, p, steps); } return 0;}a holds 3 1 4 1 5 9 2 6. First, sum the first n numbers, for n = 1 to 8.
- n
- –
- steps
- 0
Output
Describe this picture
Two pictures side by side, with the code under them. On the left, the eight cells of int a[8], holding 3 1 4 1 5 9 2 6; the first n cells are live and the rest are greyed. On the right, a plot of steps against n, from 0 to 8 across. The code pane shows the counter steps, then sum, count_equal_pairs and main, with the line about to run marked. The clip takes about 24 seconds. First the sums: for n = 1, 2 and 3 the marker i walks the live cells, each cell it reads tinted; after each n, the row the program prints drops a dot on the plot at (n, steps), ringed as it lands, in the first colour. From n = 4 the clip shows only the dots. The eight dots, (1, 1) to (8, 8), lie on a thin straight line labelled “one loop: n steps”. Then the pairs: the plot’s height rescales from 8 to 28, a second series appears, “all pairs: n(n − 1)/2 steps”, with its thin curve, and for n = 2 and 3 the markers i above and j below visit every pair. Its dots fall at 0, 1, 3, 6, 10, 15, 21 and 28 steps, rising above the straight line from n = 4. Under the pictures are one sentence on the current step and the readouts “n” and “steps”. The transport plays and pauses, steps one beat back or forward, and scrubs; a paused step is kept in the page address as counting-steps.step.
Steps, not seconds
A program’s run time depends on the machine, the compiler and what else is running. To compare algorithms, count basic steps instead: a comparison, an assignment, a read from memory. Each takes roughly a fixed time, so the count says how the time grows, and it is the same on every machine.
What matters is how the count grows with the size of the input, n. Lines of code are not the cost: one short line inside two loops can run more often than a hundred lines outside them.
The code and its cost
One loop: n steps
int sum(const int *a, int n)
{
int total = 0;
for (int i = 0; i < n; i++) {
total = total + a[i];
steps++;
}
return total;
}The loop body runs once for each of the n cells, and steps counts each run. steps is declared outside every function, as static long steps = 0;, so sum and main share it; main sets it to 0 before each call. For n = 1 to 8 the program prints 1 to 8 steps: a straight line.
All pairs: n(n − 1)/2 steps
int count_equal_pairs(const int *a, int n)
{
int pairs = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
if (a[i] == a[j])
pairs++;
steps++;
}
return pairs;
}Each pair of cells is compared once, the first cell i and a later cell j. For i = 0 the inner loop runs n − 1 times, for i = 1 it runs n − 2 times, and so on down to 0 for the last cell. The total is
For n = 1 to 8 the program prints 0, 1, 3, 6, 10, 15, 21 and 28 steps. The only equal pair is the two 1s in cells 1 and 3, counted from n = 4 on.
Up to n = 3 the pairs loop is no dearer than the sum. From n = 4 it pulls away, 6 steps against 4, and the gap keeps widening: doubling n multiplies the pairs count by about 4, and the sum’s only by 2.
Best, worst and average
Some loops stop early. A search that walks an array until it finds a key takes 1 step at best (the key is first) and n at worst (the key is last, or absent). If the key is present and equally likely to be in any cell, the average is
The average depends on which inputs are likely. It is halfway between best and worst here because every position is equally likely; any spread of positions symmetric about the middle would give the same (n + 1)/2, but a lopsided one need not.
Steps and time
A constant factor, a step that takes twice as long or a machine twice as fast, changes the time but not the shape. For large n only the growth matters: a loop over pairs on a fast machine still loses to one loop on a slow machine once n is big enough.
Worked example
A search, three ways. In 3 1 4 1 5 9 2 6, a search for 9 compares 3, 1, 4, 1, 5 and then 9: 6 comparisons. A search for 3 takes 1. A search for 7, which is absent, compares all 8. Over the eight positions, the average is (1 + 2 + … + 8)/8 = 36/8 = 4.5, which is (8 + 1)/2.
From steps to minutes. A machine does about 10⁹ basic steps a second. Summing 10⁶ numbers takes 10⁶ steps: about 1 millisecond. The pairs loop on the same 10⁶ numbers takes 10⁶ × 999,999 / 2 ≈ 5 × 10¹¹ steps: about 500 seconds, over eight minutes. On a machine ten times faster, it still takes 50 seconds, against a tenth of a millisecond for the sum.
Direct convolution. Filtering a signal of 10⁴ samples with a filter of 10³ taps multiplies every sample by every tap: 10⁴ × 10³ = 10⁷ multiplications. Fast convolution shows the route through the FFT that does far fewer.
Three checks. How many steps does the pairs loop take for n = 10? (45.) For n = 100, how many times more steps than the sum? (4,950 against 100: 49.5 times.) Doubling n multiplies the pairs count by about how much? (4.)
Where it’s used
Choosing a design. Two ways to solve a problem can be compared on paper by their step counts, before either is written.
Estimating a job. A count and a rate of steps per second say whether a job finishes in a second, overnight or never.
Spotting trouble. A loop inside a loop over the same data is the first thing to look for when a program that was fast on a small input crawls on a large one.
Reference card
| Code or idea | Meaning |
|---|---|
| basic step | a comparison, an assignment, a memory read |
| one loop over n | n steps |
| all pairs of n | n(n − 1)/2 steps |
| best, worst | the fewest and the most steps over all inputs of size n |
| average (key present, any cell alike) | (n + 1)/2 steps for a search |
| steps to seconds | steps ÷ steps per second |
| growth | what is left when constant factors are ignored |
Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.