Don't assert it.
Measure it.

A course on algorithms is mostly a list of claims: this search is O(log n), that sort is O(n log n), this one is O(n²). The usual way to teach them is to state them and draw a graph. The algorithms course on /learn does something else. Every lesson hands the code to a small engine that runs it, counts what it did, and names the growth from the counts.

The learner's own code gets the same treatment. Their answer is not compared with ours; it is measured.

Measure it yourself

These verdicts come from the engine the lessons use — nothing on this page decides them. Pick an algorithm, and move the slider to measure at larger sizes.

Binary search, merge sort and insertion sort give the same answer at every size. Counting sort does not: at the engine's default sizes its exponent is 0.42 — O(log n) territory — and the engine answers not settled. Only at sizes up to 16 000 does it name it O(n). Until this page was written it said O(log n); that is the subject of the last section.

1 · Count, don't time

The engine never looks at a clock. counted() wraps an array in a Proxy that tallies every indexed read and write, so a learner's unmodified code can be weighed.

export function counted(values) {
  const data = [...values];
  const stats = { reads: 0, writes: 0 };
  const index = (prop) => typeof prop === 'string' && /^\d+$/.test(prop);

  const array = new Proxy(data, {
    get(target, prop, receiver) { if (index(prop)) stats.reads++; return Reflect.get(target, prop, receiver); },
    set(target, prop, value, receiver) { if (index(prop)) stats.writes++; return Reflect.set(target, prop, value, receiver); },
  });

  return { array, stats, get total() { return stats.reads + stats.writes; } };
}

Here is why. The same insertion sort, timed with performance.now() at the same four sizes, five times in a row, gave exponents of −0.04, 1.96, 1.99, 2.06 and 2.01. The first run was measured while the JavaScript engine was still warming the function up: 250 items took longer than 500, and the fit came out flat. Merge sort, timed, ranged from 0.02 to 1.09. Counted, insertion sort is 2.008 — every run, on every machine, for every learner.

2 · Four sizes, doubling

A verdict needs more than one point. The engine runs the function at four sizes, each twice the last, and keeps the counts.

const DEFAULT_SIZES = [250, 500, 1000, 2000];

export function measure(fn, sizes = DEFAULT_SIZES) {   // fn(n) returns an operation count
  return sizes.map((n) => ({ n, ops: fn(n) }));
}

Doubling is what makes the table readable by eye. Linear work doubles, quadratic work quadruples, logarithmic work barely moves. Four points rather than two, because two points always fit a line and four show whether it really is one. Inputs come from a seeded shuffle, so "random" is the same random for everybody.

3 · The exponent is a slope

If the work grows as n^p, doubling n multiplies it by 2^p. Take the logarithm of the multiplier and you have p. The engine does that for each consecutive pair and keeps the median, so one odd pair cannot decide the answer.

function slopesOf(points) {                   // the exponent between each consecutive pair
  const out = [];
  for (let i = 1; i < points.length; i++) {
    const a = points[i - 1], b = points[i];
    out.push(Math.log(b.ops / a.ops) / Math.log(b.n / a.n));
  }
  return out;
}

function medianOf(values) {
  const sorted = [...values].sort((x, y) => x - y);
  const mid = Math.floor(sorted.length / 2);
  return sorted.length % 2 ? sorted[mid] : (sorted[mid - 1] + sorted[mid]) / 2;
}

export const power = (fn, sizes = DEFAULT_SIZES) => medianOf(slopesOf(measure(fn, sizes)));

4 · Name it by where the exponents fall

Real algorithms do not land on whole numbers. At these sizes a logarithm grows by about a tenth per doubling, so O(log n) measures near 0.15 and O(n log n) near 1.15. The boundaries sit between where the exponents actually fall, not on the textbook integers.

export function classify(fn, sizes = DEFAULT_SIZES) {
  const s = slopesOf(measure(fn, sizes));         // measured once; every decision reads these
  const p = medianOf(s);
  if (p < 2.5) {
    if (!steady(s)) return 'not settled';         // see the last section
    if (p < 0.08) return 'O(1)';
    if (p < 0.55) return 'O(log n)';
    if (p < 1.06) return 'O(n)';
    if (p < 1.5)  return 'O(n log n)';
    return 'O(n²)';
  }
  // …a power law has the same slope between every pair; an exponential's keep climbing
}

Measured at the default sizes: binary search 0.152, merge sort 1.16, insertion sort on shuffled input 2.008. Each is well inside its band.

5 · Exponential is told apart by its slopes

Above 2.5 the exponent alone cannot separate n³ from 2ⁿ. The shape of the slopes can: a power law has the same slope between every pair of sizes, whatever its constants, while an exponential's slopes keep climbing.

// s: the slopes classify has already measured
if (s.length >= 2 && s[s.length - 1] > 3 && s[s.length - 1] > s[0] * 1.25) return 'exponential';
return 'O(n³) or worse';

Remember that rule — climbing slopes mean the curve is not a power law yet. It turns out to matter well below 2.5.

What it costs

The toy above tallies by hand, and the two methods agree to the operation: insertion sort at 2 000 items is 2 945 343 either way. That 32× is why the engine has two ways to count. counted() weighs a learner's code without touching it, which is worth the price at lesson sizes. When the sizes grow, a lesson counts with counter() — one call where the work happens — and pays nothing.

What the measurement found

Writing this page turned up two cases where the engine returned a clean verdict and the verdict was wrong. The first is fixed in the engine now; the second is a property of counting itself. Both are worth knowing whatever tool you measure with.

A fixed cost reads as a logarithm. Counting sort over the values 0 to 1 999 has to zero and then walk its 2 000 buckets whatever n is: its cost is 4n + 4 000. At the default sizes that fixed part dominates, the slopes are 0.26, 0.42 and 0.58, the median is 0.42, and the engine named it O(log n). Plain n + 1 000 got the same verdict. Measured up to 16 000 the slopes are 0.74, 0.85 and 0.92, and the answer is O(n).

The lesson on measuring growth already told the reader to check that the multiplier is steady. The engine did not check it itself. Now it does, and classify answers not settled instead of guessing:

/* Slopes that keep climbing are not a power law yet — a fixed cost is still fading. */
function steady(s) {
  if (s.length < 3) return true;                  // two slopes cannot tell a bend from noise
  const climbing = s.every((x, i) => i === 0 || x > s[i - 1]);
  return !(climbing && s[s.length - 1] - s[0] > 0.2);
}

export const settled = (fn, sizes = DEFAULT_SIZES) => steady(slopesOf(measure(fn, sizes)));

The first version judged two slopes as well, and the course's own lab sweep caught it: quicksort on one seeded shuffle measures 0.82 then 1.41 at three sizes — noise that looks exactly like a bend — and a correct O(n log n) sort was marked unsettled. Two slopes are never judged now. On the four algorithms above the check flags counting sort at every size below 16 000 and nothing else, and all 24 labs of the algorithms course still pass. The toy's Steady reading is the engine's own settled().

Counting only sees what it wraps. A merge sort written the usual way — slice the array in two, sort each half, merge into a new array — passed through counted() measures an exponent of exactly 1.000: O(n). The Proxy wraps only the array it was given. The slices are new, plain arrays, so every read and write below the first level goes uncounted. The merge sort lesson counts comparisons through the comparator instead, which cannot be copied away.

See it in a lesson

The lesson on measuring growth builds the table by hand and then lets the engine read it.

Open the lesson ↗