Complexity From Scratch — What Big-O Actually Measures

What O(n), O(n log n) and O(n²) feel like as wall-clock time. Constant factors versus growth rate, trading time against space, and the three reasons your profiler disagrees with the textbook — assuming no prior knowledge.

The metaphor: what if the move had ten times the boxes?

Carrying 100 boxes into an apartment takes you an hour. How long for 1000?

If you said ten hours, you assumed the work scales proportionally with the number of boxes. But change the task and the answer changes. Suppose the job is "check every pair of boxes to see whether their contents overlap". Now the number of comparisons grows with the square of the count: ten times the boxes means a hundred times the work — a hundred hours.

That is the whole subject. How does the amount of work grow as the input gets bigger? Not how many seconds one item takes, but the shape of the growth.

Big-O classifies growth, not speed

Write $T(n)$ for the number of steps needed on an input of size $n$. The definition of $T(n) = O(f(n))$ is this.

In plain words: you can pick some multiplier $c$ and some threshold $n_0$ such that from there onward, $T(n)$ never rises above $f(n)$ scaled by $c$. The $c$ is the constant factor; $n_0$ marks where "we are only talking about large inputs" begins.

Three deliberate concessions are baked into that definition. Big-O states only an upper bound, it discards constant factors, and it only cares about sufficiently large $n$.

Why throw away the constant factor? Because the same algorithm runs several times faster or slower depending on language, CPU and how carefully it was written. A number that includes all of that is a one-off measurement of one machine, not a yardstick. What survives across environments is the shape of the growth — so that is the only thing we gave a name to.

Turning three growth rates into a physical sense

For rough estimation, assume a machine does something on the order of $10^8$ simple operations per second. (An order of magnitude either way is easy to get; this is about digits, not benchmarks.)

The thing to internalize: the gap between $O(n)$ and $O(n \log n)$ is practically noise. Since $\log_2 10^6 \approx 20$, you are paying a factor of twenty. Meanwhile $O(n^2)$ turns a thousand-fold increase in $n$ into a million-fold increase in work — a qualitatively different world.

The field's rules of thumb — "sorting is $O(n \log n)$, so treat it as almost linear" and "flinch when you see a nested loop" — come straight out of that table.

Constant factors and growth rate are different claims

"Better complexity means faster" is only true for sufficiently large $n$.

Compare $T_A(n) = 100n$ with $T_B(n) = n^2$. They tie at $n = 100$, and below that the asymptotically worse B wins. At $n = 10$ it is $T_A = 1000$ against $T_B = 100$ — a factor of ten in the "wrong" direction.

This is not a blackboard curiosity. Drop a "smart" data structure onto an array of a few dozen elements and the constants for hashing and pointer chasing get charged in full, losing to a plain linear scan. It is the same reason standard-library sorts switch to insertion sort on small ranges. Before optimizing for growth, check that you are actually in the regime where growth dominates.

Time and space are tradeable

Complexity is not only about time. Space complexity — memory consumed — uses the same notation, and the two can usually be exchanged for each other.

Buying time with memory means storing results so you never recompute them: build an index, keep a cache, memoize intermediate values. All of it says "if you keep a table, lookup replaces work", and dynamic programming is the most systematic version of that idea.

Buying memory with time runs the other way. Gradient checkpointing in deep learning deliberately throws away activations computed in the forward pass and recomputes them when the backward pass needs them. Compute goes up, memory drops sharply, and a model that would not fit suddenly does (Backpropagation).

When someone says "make it faster", the first question to ask is whether there is spare memory to spend.

Worst case, average case, amortized

The same algorithm yields different numbers depending on which promise you are making.

• Worst case: an upper bound that no input can break. Quicksort is $O(n^2)$ in the worst case
• Average case: the expectation over random inputs. Quicksort is $O(n \log n)$ on average, and in practice that is the number that governs
• Amortized: total cost of a sequence of operations divided by the number of operations. Appending to a dynamic array costs $O(n)$ on the occasional resize, but because capacity doubles, the amortized cost is $O(1)$

When people say hash table lookup is "$O(1)$", that is the average too; the worst case is $O(n)$. State which promise you mean, or two people will argue past each other.

Three reasons your profiler disagrees with the theory

You fix the complexity and nothing gets faster — or something is faster than the math says. This happens constantly, and it is almost always one of three things.

1. The memory hierarchy Big-O prices every "step" identically. Real hardware does not: data sitting in L1 cache arrives in a few cycles, while a trip to main memory costs hundreds. Two $O(n)$ traversals — one sweeping a contiguous array, one chasing pointers through nodes scattered across the heap — can differ by an order of magnitude in wall-clock time. Of course they do: the price of a "step" varies by 100×.

2. Branch prediction Modern CPUs guess the outcome of a conditional and run ahead. A correct guess is nearly free; a wrong one throws away a dozen-odd cycles of speculative work. This is why the famous benchmark where an if over a sorted array beats the same if over an unsorted one exists. Identical step counts, different predictability.

3. Constants and what a "step" contains Allocation, bounds checks, function call overhead, dynamic dispatch. Whether the $n$ in $O(n)$ means "advance a pointer" or "construct an object" changes the real seconds enormously while leaving the formula untouched.

So the order of operations never varies. Fix the complexity first ($n^2$ to $n \log n$). Only then profile and shave the constants. Do it backwards and you will spend a day on cache locality before noticing there was one loop too many all along.

Hands on: measure the growth

You can estimate the exponent by doubling $n$ and watching what the time does.

import time

def timeit(fn, n):
    t = time.perf_counter()
    fn(n)
    return time.perf_counter() - t

def quadratic(n):                  # the canonical O(n^2): a nested loop
    s = 0
    for i in range(n):
        for j in range(n):
            s += 1

for n in (500, 1000, 2000):        # double n each time
    print(n, round(timeit(quadratic, n), 3))

Roughly 4× per doubling means $O(n^2)$; roughly 2× means $O(n)$; a little more than 2× means $O(n \log n)$. Take at least three points — with only two, an additive constant will skew the ratio and you will misdiagnose.

Four things that matter in practice

1. Know your $n$ first Before calling something slow, look up how many items it actually handles. If $n$ tops out at 100, the whole complexity discussion may be irrelevant.

2. Suspect nested loops and nested lookups Most performance bugs are a list being searched inside a loop over another list. Replacing that inner linear scan with a dictionary turns $O(n^2)$ into $O(n)$.

3. Measure before shaving Once the complexity is right, optimize strictly from the top of the profiler's list. Human guesses about bottlenecks are wrong more often than not.

4. Write down which case you designed for Structures that are "$O(1)$ average, $O(n)$ worst" bare their teeth on adversarial or skewed input. Leave a comment saying which assumption you relied on.

Summary

• Big-O measures growth, not speed; it deliberately discards constant factors and small $n$
• $O(n)$ versus $O(n \log n)$ barely matters in practice. $O(n^2)$ changes the number of digits
• For small $n$ the asymptotically worse algorithm can win: $T_A = 100n$ and $T_B = n^2$ cross at $n = 100$
• Time and space trade against each other — memoization and indexes buy time with memory, gradient checkpointing does the reverse
• Profilers diverge because of cache, branch prediction and constants. Fix the order first, then measure and shave

Next: the tools you actually use to pick a growth rate — arrays, hashes, trees and heaps, and what each one gives up (Choosing a Data Structure).