Big O Is a Model, Not a Stopwatch

Big O notation answers a narrower question than “Which program is faster?” It describes an asymptotic upper bound on how a cost grows with input size under a chosen model. That makes it useful — and easy to misuse.

Name the input and the operation

O(n) is incomplete without saying what n means and which operation is counted. A dictionary lookup may be expected constant time under assumptions about hashing and distribution. Traversing every item is linear in item count. A graph algorithm may depend on both vertices and edges.

The model becomes useful when its variables correspond to a real workload.

Constants disappear from notation, not from machines

Two linear algorithms can have very different costs. One may scan contiguous memory; another may follow pointers, allocate objects, and trigger cache misses. For the input range a service actually sees, those constants can dominate.

This does not invalidate asymptotic analysis. It explains why analysis and measurement answer different questions:

Worst case is a design conversation

Average behavior can be attractive while a worst case remains operationally dangerous. A request boundary that accepts unbounded input turns algorithmic growth into a capacity and abuse question. A quadratic comparison may be harmless for ten configuration entries and catastrophic for an unbounded payload.

State the expected, maximum, and adversarial sizes. Then decide whether to change the algorithm, bound the input, precompute, stream, or accept the cost.

Space is part of the model

Time improvements often spend memory. A lookup table may turn repeated scans into constant-time queries at the cost of storage and invalidation. Copying a collection may simplify ownership while increasing peak memory. An honest analysis names both dimensions and the lifecycle of auxiliary data.

Measurement needs a hypothesis

A benchmark without a question produces numbers that are easy to decorate and hard to interpret. Define the operation, input distribution, runtime mode, warm-up, allocation behavior, and excluded costs. Compare implementations only when they solve the same problem.

Big O prevents surprise about growth. Measurement prevents surprise about the machine. Good performance work needs both, plus enough domain knowledge to know which input sizes matter.