A nightly job took 40 minutes last month and takes two hours forty on twice the data. What do you conclude about its complexity, and what would you measure next?

What the ratio does and does not tell you

Start with the arithmetic, because it is the part that has a right answer. If the cost is well modelled by a constant times n to the power k, then doubling n multiplies the cost by 2 to the power k. Forty minutes to a hundred and sixty is a factor of four, and 4 is 2 squared, so k is 2 and the observation is consistent with quadratic growth.

That word "consistent" is the whole of the answer. Two measurements determine a straight line through two points on a log-log plot and therefore fit exactly one power law, but they also fit a linear cost with a step function added, a linear cost that has just crossed a memory threshold, and a linear cost measured on a machine that was busy the second time. A candidate who says "it is quadratic" has over-claimed from two data points; a candidate who says "that is the signature of quadratic growth, and here is how I would confirm it" has given the answer being scored.

It is also worth being precise about what each class predicts for a doubling, because these numbers are what you compare your ratios against. Linear predicts 2. Quadratic predicts 4, cubic 8. The interesting one is n log n, which predicts slightly more than 2: at a starting size around a million the ratio is 2 times 21 over 20, roughly 2.1, and that closeness to linear is exactly why n log n and linear are hard to separate empirically and easy to separate by reading the code.

The doubling series

The measurement to ask for is not a bigger benchmark, it is more of them. Run the job on a quarter, a half, and the whole of a month's data, on the same machine, with the same cache state, and take the successive ratios. A power law gives you a flat ratio series: 4, 4, 4. A cliff gives you a series with one anomaly in it and normal ratios either side.

Two details make the difference between a measurement and a number. The first is that each size must be a genuine sample of the real data rather than the first quarter of the file, because real datasets are not homogeneous and the first quarter of a log is often the quiet hours. The second is to control the state you are not varying: a cold page cache on run one and a warm one on run two can produce a ratio that has nothing to do with the algorithm. State which of these you controlled; an interviewer is listening for whether you know that a benchmark is an experiment with confounds and not a stopwatch reading.

Cliffs that masquerade as exponents

The rival explanation for a fourfold jump is that some resource stopped being sufficient. A sort that fitted in the heap and now spills to disk, a hash table that outgrew a cache level, a working set that crossed the point where the garbage collector starts running back to back, a batch that now exceeds a connection pool and begins to serialise. Each of these is a large constant-factor change with a threshold, and each will look like a higher exponent if you only sample either side of the threshold.

The way to tell them apart is that a cliff is not reproducible as a ratio. Sample above the threshold twice and the ratio drops back towards linear, because the extra constant is already being paid at both sizes. Sample below it twice and it is also linear. Only a pair that straddles it is inflated. That is the single explanation you should reach for when a ratio series reads 2.1, 2.1, 2.1, 9.

Size is not the only input

Asymptotic notation is a function of size, and it quietly encourages the assumption that size is the only thing that varies. Plenty of real algorithms have costs that depend on the shape of the data instead: quicksort on already sorted input with a naive pivot, a hash table under keys engineered to collide, a graph traversal on a dense component, a regular expression on a string constructed to force backtracking. For these the average case and the worst case are different functions, and the average case is the one your benchmark measured.

So the second question to ask, after the doubling series, is who supplies the input. If the answer is an internal upstream job, the observed distribution is probably representative and the average case is the relevant one. If the answer is an end user or a partner API, then the worst case is not a theoretical curiosity, it is a thing someone can choose to hand you, and you should bound and cap accordingly. This is where a length limit, a work budget with a timeout, or a switch to an algorithm with a worst-case guarantee earns its place.

What this failure looks like in the wild

In July 2019, Cloudflare deployed a firewall rule whose regular expression backtracked catastrophically, and CPU usage saturated across its global edge within minutes. This is the practical case for asymptotic analysis on inputs you do not control: the rule was correct, it passed review, and the cost only appeared on inputs shaped to force exponential backtracking. When you state a complexity in an interview, state it for the worst case and say who supplies the input.