Big-O notation: growth, not speed

There are two standard ways to explain Big-O notation, and both fail the reader. One is a table of names to memorise — constant, logarithmic, linear, quadratic — which tells you what the words mean but not how to arrive at them. The other is a formal treatment with limits and epsilons, which is rigorous and answers a question almost nobody asked.

What you actually want is the ability to look at a function you have just written and say what it will cost when the input gets large, plus the judgement to know when the notation is quietly misleading you. That is what this is for.

The question is about growth, not speed

Big-O does not measure how fast code runs. It measures how the work grows as the input grows, which is a different and more durable question. A faster machine changes every timing on this page; it does not change any of the shapes.

This is why the notation earns its keep. A function that handles a hundred items instantly and takes twenty minutes on a million has not got slower — it has revealed the shape it always had. The shape was visible in the code before you ever ran it, and that is the skill worth acquiring.

Here is what the common shapes cost in operations, which is the table worth internalising because it shows where the cliff is:

Read the last column slowly, because it contains the whole argument. At a million items, an O(n log n) algorithm does about twenty million operations — a couple of hundredths of a second on any modern machine. An O(n squared) algorithm on the same input does a trillion, which at a billion operations a second is roughly seventeen minutes. Same input, same hardware, same problem. The difference is not tuning, and no amount of profiling recovers it. Meanwhile O(log n) reaches twenty operations at a million items, which is why binary search feels like cheating.

Why constants get dropped, and when that lies to you

The convention is to discard constant factors and lower-order terms: 3n + 50 becomes O(n), and n squared over two becomes O(n squared). The justification is that as n grows, the dominant term swamps everything else, so keeping the rest tells you nothing about the shape.

That is sound, and it is also an abstraction with a real cost, which most introductions decline to mention. Two honest caveats:

For small n, the constant is often the entire story. This is not a technicality — it is why production sorting implementations switch to insertion sort for small partitions. Insertion sort is O(n squared) and beats O(n log n) algorithms on twenty elements, because twenty is not large and its constant is tiny. If your input is always small and always will be, complexity analysis is answering a question you do not have.

Memory locality can beat a better shape. A linear pass over contiguous memory can outperform an algorithm with a better complexity class that chases pointers around the heap, because a cache miss costs a hundred times what a cache hit costs, and Big-O counts both as one operation. Real measured behaviour on real data is the arbiter; Big-O tells you what to expect as things scale, not which of two implementations is faster today.

Hold both ideas at once. The notation is the right tool for reasoning about growth and the wrong tool for benchmarking.

Analysing code without guessing

Analysis is mechanical once you know the rules. There are only four worth memorising.

Sequential blocks add. A loop over n followed by another loop over n is O(n) + O(n) = O(2n) = O(n). Two passes is still linear.

Nested loops multiply. A loop over n containing a loop over n is O(n squared). A loop over n containing a loop over m is O(n * m) — and note those are different, which matters when one collection is tiny and the other is huge.

Halving or doubling is logarithmic. If the index doubles each step, or the search space halves, the loop runs about log base 2 of n times. That is the signature of binary search and of tree descent.

Watch for hidden loops. This is where real code goes wrong. A membership test looks like one operation, but its cost depends entirely on the container: constant for a set, linear for a list. So this function is quadratic, and nothing in its shape says so:

def common_slow(a, b):    result = []    for x in a:            # n iterations        if x in b:         # `in` on a LIST scans: m operations            result.append(x)    return result          # O(n * m)

One character changes the complexity class:

def common_fast(a, b):    b_set = set(b)         # O(m) once    return [x for x in a if x in b_set]   # `in` on a SET is O(1) -> O(n + m)

That pattern — a linear scan hiding inside a loop — is the most common accidental quadratic in working code, and it is invisible unless you have trained yourself to ask what each operation actually costs.

Watching a quadratic happen

Theory is more convincing when you can see it. Two functions that answer the same question, timed on the same machine as n doubles:

def has_duplicate_quadratic(items):    for i in range(len(items)):        for j in range(i + 1, len(items)):            if items[i] == items[j]:                return True    return Falsedef has_duplicate_linear(items):    seen = set()    for x in items:        if x in seen:            return True        seen.add(x)    return False

Run against inputs with no duplicates, so both do their full work:

      n    quadratic     linear    ratio   1000        6.1ms     0.02ms     329x   2000       24.2ms     0.04ms     594x   4000       99.5ms     0.07ms    1425x   8000      402.7ms     0.18ms    2252x

Those are measurements from one laptop and will differ on yours, but the pattern is the point and it will hold everywhere. Each time n doubles, the quadratic version takes roughly four times as long — 6, 24, 99, 402 — because doubling the input quadruples n squared. The linear version roughly doubles. The ratio between them is not fixed; it grows without limit. Extrapolate: at n = 100,000 the quadratic version needs about a minute, and at a million it needs a couple of hours.

Notice also that the quadratic version is not badly written. It is the obvious solution, and it is correct. It simply has a shape that cannot survive scale.

A nested loop that is not quadratic

The rule that nested loops multiply is a good default and a trap if applied blindly. Consider a scan with two indices moving through the same array:

def longest_run_within(values, limit):    """Longest window whose max minus min stays within limit (sorted input)."""    left = 0    best = 0    for right in range(len(values)):        while values[right] - values[left] > limit:            left += 1                     # inner loop        best = max(best, right - left + 1)    return best

There is a loop inside a loop, so the instinct says quadratic. It is O(n). The reason is that left never decreases. Across the entire run it advances at most n times in total, no matter how the iterations are distributed. So the inner loop's total work over the whole function is bounded by n, not by n per outer iteration.

The lesson generalises: do not count nesting depth, count total work. Ask how many times each statement executes over the whole run, not how deeply it is nested. This is the reasoning behind two-pointer and sliding-window techniques, and it is the single most common place where a correct analysis looks wrong at first glance.

Best, average and worst are three questions

"What is the complexity" is underspecified, and the three answers can differ enough to change a decision.

Take a linear search. Best case the target is first, which is O(1). Worst case it is absent, which is O(n). Average case, assuming it is present and uniformly positioned, is n/2 — still O(n), because constants drop.

Quicksort is the more instructive example. Average case O(n log n), worst case O(n squared) when the pivot choice is consistently terrible against already-sorted input. That gap was not academic: it was a real denial-of-service vector, which is why implementations randomise pivots or detect degenerate cases and fall back.

Which one you should care about depends on what you are protecting. For a user-facing latency budget, the worst case is what shows up in your ninety-ninth percentile. For throughput over a batch, the average dominates. If an adversary picks your input, only the worst case is real.

Doubling, and why amortised O(1) is honest

Appending to a dynamic array is described as O(1), which looks like a lie: the array has a fixed capacity, and when it fills, everything must be copied to a bigger block. That copy is O(n). So how is append constant?

Because of how the capacity grows. Doubling makes the expensive copies rare enough that their cost, spread across all the cheap appends, is a constant. That is what amortised means, and it is a real guarantee rather than an averaging trick. Here is the arithmetic, counting how many elements get copied in total:

def growth_cost(n, mode):    cap, resizes, copied = 1, 0, 0    for i in range(n):        if i >= cap:            copied += cap                 # every existing element moves            cap = cap * 2 if mode == "double" else cap + 100            resizes += 1    return resizes, copied

The results make the case better than any explanation:

n=1,000,000  doubling      resizes=     20  copied=     1,048,575  copies/append=    1.0n=1,000,000  grow by 100   resizes= 10,000  copied= 4,999,510,000  copies/append= 4999.5

With doubling, a million appends copy about a million elements in total — one copy per append, and that ratio stays flat as n grows, which is exactly what O(1) amortised claims. Growing by a fixed hundred copies five billion elements for the same million appends, and the per-append cost is not constant at all: it rises with n, making the whole sequence quadratic. Doubling works because the capacity grows in proportion to what is already there, so the work between expensive events grows too.

Space, including the stack you forgot

Space complexity follows the same rules, applied to memory rather than operations, and beginners consistently miss one source of it: recursion allocates a stack frame per call, and that memory is as real as an array you allocated yourself.

def total_iterative(items):        # O(1) extra space    running = 0    for x in items:        running += x    return runningdef total_recursive(items, i=0):   # O(n) space: n frames live at once    if i == len(items):        return 0    return items[i] + total_recursive(items, i + 1)

Both are O(n) in time. The second holds n frames simultaneously, so on a large list it does not merely run slowly — it fails outright with a recursion-depth error. That is a crash on valid input, which makes it a correctness problem rather than a performance one.

Also count what you allocate rather than only what you return. Building a set of every element to answer a yes-or-no question is a deliberate trade: O(n) memory bought O(n) time instead of O(n squared). Usually a good trade, and worth making knowingly.

What this changes about how you write code

Three habits carry most of the value.

Find the dominant term and stop worrying about the rest. A function with a linear pass, a sort, and another linear pass is O(n log n) — the sort dominates, and optimising the linear passes is wasted effort.

Learn the cost of your containers well enough that hidden loops become visible. Membership in a list is linear; in a set or dictionary it is constant. Inserting at the front of an array shifts everything. Sorting is n log n, so sorting inside a loop over n items is n squared log n, which is almost always a mistake.

And know when to stop. If n is bounded and small — a config file, a list of countries, a fixed set of retry attempts — the quadratic solution is often clearer and its cost is genuinely irrelevant. Complexity analysis is for identifying which parts of your program will fall over as data grows, so you can spend your attention there and leave everything else readable.