Measuring growth

The doubling test

This works because for a power law, doubling n multiplies the work by 2^p where p is the exponent. Measure the multiplier, take the logarithm, and you have p: 1 is linear, 2 is quadratic. That is exactly what classify does.

Count operations, not milliseconds

counted returns a proxy, so existing code runs through it unchanged. Write a sort the normal way, hand it c.array, and the tally appears without a single line of instrumentation inside the algorithm.

const t = counter();          // for work you count yourself
for (const x of items) { t(); compare(x); }
t.count();                    // 1 per item

const c = counted(items);     // an array that tallies its own reads and writes
const a = c.array;            // use it exactly like an array
a[0]; a[1] = 5;
c.stats;                      // { reads: 1, writes: 1 }  — a.length is not counted
c.total;                      // 2

Reading a real measurement

Four, every time. That is a quadratic, and no amount of reading the source could have told you as certainly. When the multiplier is not steady, the algorithm has more than one behaviour in it — which is usually the interesting part.

    n      ops     ×
  250    186 k     —
  500    746 k   4.01
 1000  2 987 k   4.00
 2000 11 950 k   4.00        →  O(n²)

Choosing the sizes

• Big enough that the constants stop mattering. At n = 10, setup costs dominate and everything looks flat. If they have not faded, classify says so: when the slopes are still climbing it returns "not settled" instead of a name — measure at larger sizes.
• Doubling. Any ratio works for the fit, but doubling makes the table readable by eye.
• Four points, not two. Two points always fit a line; four show you whether it really is one.
• The same data every time. randomInts(n, seed) and shuffled(n, seed) are seeded, so a measurement is reproducible — an unseeded shuffle makes quicksort look different on every run.

Where this is going

From here on, every lesson measures. When the sorting lessons claim insertion sort is O(n²) and merge sort is O(n log n), you will not be asked to believe it — the lab will hand both of them the same input and print the multipliers.

And the habit transfers: the fastest way to find out why a real function is slow is to run it at two sizes and look at the ratio. Most performance surprises are a growth rate nobody checked.