Big-O: Measuring Cost Without a Stopwatch

1Why a stopwatch is the wrong instrument

Timing is the obvious way to compare two algorithms. It is also almost useless for the question we actually care about.

Suppose I tell you my sorting function takes 0.4 seconds. What have you learned?

Almost nothing. You do not know my CPU, whether the machine was busy, which language I used, whether the compiler optimised the loop away, how big the input was, or whether the data was already nearly sorted. Run the same code on a phone and a server and you get numbers ten times apart.

Worse: a measurement at one input size does not predict another. An algorithm that is faster on a thousand items can be catastrophically slower on a million. If you only ever measure the thousand, you will ship the wrong one.

2Counting operations

Before the notation, the habit: look at a loop and say how many times its body runs, in terms of n.

Call the size of the input n. For a list, that is its length; for a string, its number of characters; for a graph, usually its vertices and edges. Then count.

def f1(xs):                 # n = len(xs)
    return xs[0]            # 1 operation, whatever n is        → O(1)

def f2(xs):
    total = 0               # 1
    for x in xs:            # the body runs n times
        total += x          #   1 operation each  → n
    return total            # 1
                            # total: n + 2  → O(n)

def f3(xs):
    for a in xs:            # n times
        for b in xs:        #   n times each
            print(a, b)     #     1 operation  → n × n
                            # total: n²  → O(n²)

def f4(xs):
    for a in xs:            # n times
        pass
    for b in xs:            # n more times — SEPARATE, not nested
        pass
                            # total: 2n  → O(n)

Two rules cover most cases and are worth saying out loud:

• Nested loops multiply. A loop inside a loop, each over n items, runs n × n times.
• Sequential loops add. One loop after another is n + n, which is 2n, which is still O(n).

That second one catches people out. Two passes over the data is not “twice as bad a complexity.” It is the same complexity, and typically not worth contorting your code to avoid.

3Big-O and its two simplification rules

Now the notation. It is deliberately crude, and the crudeness is the point.

O(f(n)) means: as n grows large, the cost grows no faster than f(n), up to a constant factor. Two rules follow, and they are the whole of the notation in practice.

Rule 1 — drop constant factors

O(3n) is written O(n). O(n/2) is written O(n).

This looks like vandalism. The justification: the constant depends on things we deliberately refuse to model — your CPU, your language, whether the loop body has two statements or six. A machine three times faster turns 3n into n. It cannot turn n² into n.

Rule 2 — keep only the dominant term

O(n² + n + 50) is written O(n²).

The smaller terms do not just become less important — they become invisible. By a million items, everything except n² is rounding error.

Here are the seven curves you will actually meet, racing each other. Watch how they are indistinguishable at small n and then separate violently:

4Best, worst, average — and amortised

“What is the complexity of linear search?” is an incomplete question. It depends which case you mean.

Take linear search. The target could be first, last, or absent:

• Best case is usually useless. Every algorithm has a lucky input. Quoting it is marketing, not analysis.
• Worst case is the default, and the one meant when nobody says otherwise. It is a guarantee: this will never be slower than that.
• Average case needs an assumption about the distribution of inputs, which is why it is quoted less often — but it is why quicksort is used in practice despite its O(n²) worst case.

Amortised: the fourth one, and the interesting one

Some operations are usually cheap and occasionally expensive, in a pattern where the expensive ones are rare enough to pay for themselves. Appending to a Python list is the standard example. Watch it:

Most appends write one slot. Every so often the array is full, a block twice the size is allocated, and everything is copied. That append costs O(n).

But the expensive ones get rarer as the array grows — they happen at sizes 1, 2, 4, 8, 16, 32... The total copying work across n appends comes to roughly 2n, so the average cost per append is constant. That is amortised O(1).

5Space complexity, and the memory you forgot

Time is not the only bill. And recursive functions charge for memory in a way that catches almost everyone.

Space complexity counts the extra memory an algorithm needs, beyond the input it was handed. An algorithm using O(1) extra space is called in‑place.

def reverse_copy(xs):        # O(n) space — builds a whole second list
    out = []
    for x in reversed(xs):
        out.append(x)
    return out

def reverse_inplace(xs):     # O(1) space — three variables, whatever n is
    lo, hi = 0, len(xs) - 1
    while lo < hi:
        xs[lo], xs[hi] = xs[hi], xs[lo]
        lo += 1
        hi -= 1

The one people miss: the call stack

Every function call in progress occupies a frame in memory. A recursive function that goes n levels deep is using O(n) space — even if it allocates nothing itself.

def total(xs):
    if not xs:
        return 0
    return xs[0] + total(xs[1:])     # ← two hidden costs, not one

# 1. O(n) stack frames: n calls are open at once before any returns.
# 2. xs[1:] COPIES the rest of the list, every single call.
#    n copies of average length n/2 → O(n²) time as well.
#
# On a list of 10,000 this raises RecursionError before it gets slow enough
# for you to notice the second problem.

In the animation above, the depth of the tree is the peak stack usage. That is why the space complexity of naive Fibonacci is O(n) even though its time complexity is O(2ⁿ) — the tree is wide, but only one root-to-leaf path is open at a time.

6Reading complexity off real code

The skill is not reciting definitions. It is looking at forty lines you did not write and saying which curve they are on.

A procedure that works nearly every time:

1. Find the loops. Nested multiply, sequential add.
2. Look inside each loop for hidden loops — in on a list, sorted(), slicing, string concatenation, a function call that itself loops.
3. Ask how the loop variable changes. i += 1 gives n iterations. i *= 2 gives log n. That single character is the whole difference.
4. Drop constants, keep the biggest term.

# --- What is this? ---
def mystery(xs):
    seen = []
    for x in xs:              # n iterations
        if x not in seen:     # ← O(len(seen)) — up to n
            seen.append(x)
    return seen
# n iterations × O(n) membership test = O(n²).
# Fix: make `seen` a set. Same lines, O(n).


# --- And this? ---
def mystery2(n):
    count = 0
    i = 1
    while i < n:              # i doubles: 1, 2, 4, 8, ...
        count += 1
        i *= 2                # ← the multiplication is the whole story
    return count
# i reaches n after log₂(n) doublings → O(log n).


# --- And this? ---
def mystery3(xs):
    for x in xs:              # n
        for y in xs:          #   n
            for z in xs:      #     n
                if x + y + z == 0:
                    return True
    return False
# O(n³). On 1,000 items that is a billion iterations — about a second.
# On 10,000 it is a thousand seconds. Chapter 4 does this in O(n²).

>_Playground

Count the operations yourself. Each function below has a counter wired into it — run it at several sizes and see whether the numbers match the curve you predicted.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.