Measuring Efficiency

Measuring Efficiency

There are exactly two ways to know which of two algorithms is faster, and they answer different questions. You can measure it — run both, time them — or you can analyze it — count how the work grows with input size. Beginners reach for the stopwatch and stop there. This page is about why that is a trap, where the stopwatch is genuinely the only tool that works, and the precise point at which the two methods disagree.

The one-sentence version: analysis tells you which algorithm wins as the data grows; measurement tells you which wins on the data you have today. These are not the same algorithm, and confusing them ships slow software.

The two rulers, and what each cannot see

A benchmark that says "algorithm A is faster" is really saying "A is faster on this input, on this CPU, today." That is why "faster on my machine" is not a complexity claim. A slow language running a lower-class algorithm crushes a fast language running a higher-class one — but only once the input is big enough, and a single benchmark cannot tell you whether you are past that point. The growth classes themselves and the formal definition are catalogued on Functions and Their Growth Rates and Big-O Notation.

The crossover: where constants beat the better class (worked)

This is the single most important number in this topic and the reason you need both rulers. Compare two sorts:

• A — an in-place, cache-friendly O(n2) like insertion sort. Tiny constant; model its cost as TA(n) = n2.
• B — an O(n log n) mergesort, but paying a fat per-element constant for allocation, recursion, and pointer-chasing. Model it as TB(n) = 50 · n · log2n.

Analysis says B wins — eventually. But when? Set the costs equal:

n2 = 50·n·log2n  ⇒  n = 50·log2n

Solve numerically: at n = 430, 50·log2430 ≈ 437 — still larger than n, so A is faster. At n = 440, 50·log2440 ≈ 439 < 440 — B pulls ahead. The crossover is n* ≈ 440. For every input below ~440 elements, the "worse" quadratic algorithm is genuinely faster; only above it does the better class matter. Benchmark on n = 100 and you would confidently ship the O(n2) and get destroyed in production at n = 105; trust analysis alone and you would ship the mergesort and be needlessly slow on every small array. Only using both is correct — which is exactly why real sort libraries are hybrids that fall back to insertion sort on small subarrays and switch to an O(n log n) method above a measured threshold.

Step through the growth curves interactively below — watch how the flat and linear classes stay glued to the axis while the quadratic and exponential curves become walls. The interactive plots the classes; the crossover above is what a real benchmark of two implementations would reveal on top of them.

Benchmarking honestly — the traps that fake a measurement

Because a benchmark is one point on the constant×class curve, a sloppy benchmark lies confidently. The discipline:

• Measure across sizes, not one size. A single n tells you nothing about growth. Time at n, 2n, 4n, 8n and watch the ratio: ~2× per doubling is linear, ~4× is quadratic. The slope is the empirical growth class.
• Warm up first. On JIT runtimes (JVM, V8) the first runs execute interpreted, cold-cache code; timing them measures the compiler, not the algorithm. Discard warmup iterations.
• Benchmark the worst case, not a lucky input. Quicksort on already-sorted data hits its O(n2) path; a random-input benchmark hides it.
• Isolate the machine. Background load, CPU frequency scaling, and garbage collection add noise that can dwarf the effect you are measuring — take medians of many runs, not one wall-clock reading.
• Remember the cache. Two same-class algorithms can differ several-fold purely on memory-access pattern — a constant the analysis dropped but the profiler exposes (see the cost-model discussion on Introduction to Algorithm Analysis).

Key takeaways

• Two rulers, two questions. Analysis ranks algorithms as data grows; benchmarking ranks them on today's input. Neither alone is enough.
• "Faster on my machine" is not a complexity claim — it is a single point on a constant×class curve and says nothing about scale.
• The crossover is real and computable: an O(n2) with a tiny constant beats an O(n log n) with a 50× constant up to n ≈ 440 — which is why production sorts are hybrids.
• Benchmark across sizes, warm up, use the worst case, take medians — measure the growth slope, not one lucky number.