Don't Memorize Big-O — Double the Input and Measure

In one line

"This function is O(n)" is not something you say from memory; you say it after measuring. If you double the input and see how many times larger the time gets, a hidden quadratic shows up, and if you look at the distribution of repeated measurements, you can tell whether "it got faster" is noise or an improvement.

Why this was needed

It is common for a deduplication that took 0.1ms for 100 items in staging to take several seconds when it meets 50,000 items in production (an example). Not one line of code changed, and all the tests were green. That is because even a quadratic function is fast on small input. The problem is not "how fast is it" but "how does it grow as the input grows," and a single measurement cannot answer that question.

Judging only from the shape of the code is wrong in the other direction too. A double loop whose inner loop always runs three times is linear, and a one-liner with no loop, if x not in seen:, scans the list from the beginning if seen is a list. The TimeComplexity wiki lists, for CPython, x in s, insert, and pop of a middle element on a list as O(n), and x in s on a set as O(1) on average (O(n) in the worst case). Here n is the number of elements the container holds right now, and it multiplies when called inside a loop.

How it works

The doubling experiment. If the time is roughly c·n^k, then t(2n)/t(n) ≈ 2^k. A ratio near 2 means linear, near 4 means quadratic, and near 8 means cubic. You read the exponent as log2(ratio). An n log n function goes only slightly above 2 when doubled once, so it is hard to tell from linear this way, and this lab only distinguishes linear from quadratic. Increase the size several times, such as n, 2n, 4n, 8n, get three ratios, and use their median as the representative value; if you look at just one pair, a single piece of noise can flip the conclusion.

The clock. time.perf_counter is the clock that gives the highest resolution for measuring short intervals, and only the difference between two readings is meaningful. In CPython it is a clock that never goes backward (monotonic). On the other hand, the documentation says that time.time() can return a smaller value than before if the system clock is adjusted backward. You can ask directly which clock is adjustable with time.get_clock_info(), through its adjustable·monotonic fields.

Repetition and representative values. If you measure the same code seven times, you get seven different numbers. The timeit documentation says that computing the mean and standard deviation of repeated results is not very useful. The reasoning is that the smallest value is the lower bound of what that machine can do with that code, and the large values are usually caused by interference from other processes, not by Python. So in this lab, when looking at the growth rate of the code itself (the doubling ratio), you divide minimums by minimums. On the other hand, when reporting a before-and-after comparison, you write down the median together with the distribution. As the statistics.median documentation puts it, the median is a representative value that is less shaken by outliers, and the fact that the two distributions do not overlap (the slowest sample after the improvement is faster than the fastest sample before it) is much stronger evidence than a pair of means. By default, timeit turns off garbage collection while measuring, and the default repeat count is 5.

There is one more thing a measuring tool must observe: it does not measure the time spent building the input. If the time to build the input in linear time gets mixed in, the ratio of a quadratic function comes out below 4 and hides the quadratic. And because some functions modify their input, you build the input fresh for every repetition.

Three hidden quadratics. They are in on a list, list.insert(0, x), and repeatedly concatenating immutable sequences. The common sequence operations documentation says that concatenating immutable sequences always creates a new object, so repeated concatenation costs quadratic time in the total length, and it names str.join() or io.StringIO for str, and bytes.join()·io.BytesIO·bytearray for bytes, as alternatives. CPython sometimes optimizes a += b for str, but PEP 8 says that optimization is fragile even in CPython and does not exist at all in implementations that do not use reference counting, so you should not rely on it. That is why this lab measures bytes instead of str.

What to keep when you fix it. Replacing deduplication with list(set(items)) makes it faster, but a set is an unordered collection, so the result order changes. For dict, insertion-order preservation has been part of the language specification since 3.7, so dict.fromkeys(items) keeps the order of first appearance. If the faster function gives a different answer, that is not an improvement but a bug.

What it looks like in the field

If a performance PR says "I measured once locally and it was 12% faster," that number does not prove anything yet. You have to ask together how many times it was measured under the same conditions, whether the before and after distributions overlap, and what happens when the input grows tenfold. Once you get the exponent from a doubling experiment, you can extrapolate "if 8,000 items take 0.2 seconds now, how many seconds will 100,000 items take," and compare that number with the budget to decide whether to fix it now. Extrapolation rests on the assumption that the same growth rate continues, so at the point where the data exceeds the CPU cache, the ratio itself may change. That topic belongs to the "Computer Architecture" course. Profiling to find where it is slow (tottime and cumtime of cProfile) is covered by the "Diagnosing CPU and Memory Leaks" course, and putting load on the whole service and judging regressions by percentiles is covered by the "Load Testing" course. This module is the place in between where you measure the growth rate of a single function.

What you will do in the next lab

After asking the Pod directly about the properties of the two clocks, you will build a measuring tool that produces repetitions, medians, and minimums. You will measure five functions with hidden complexity at four sizes, get the ratios and exponents, and separate linear from quadratic. You will fix the most common quadratic, deduplication, while preserving order, compare before and after as distributions, and then extrapolate how many seconds it would take at 100,000 items and compare it with the budget.