🧩 Data Structures & Algorithms · Chapter 1

Big-O: how fast code grows

Two programs both take one second on 1,000 items. On a million items, one takes about 17 minutes and the other takes eleven days. Big-O tells you which is which before you run either.

Study this lesson free in the app →

The basics

Big-O describes how the work a piece of code does grows as its input grows — not how many seconds it takes on your laptop.

The problem it solves: speed on a small test tells you almost nothing. Code that handles 100 items instantly can freeze on 100,000. Big-O lets you compare two approaches on paper, before you write or run either, by asking one question: if the input doubles, what happens to the work?

The mental model: looking up a word in a paper dictionary. Reading page by page from the front is linear — a dictionary twice as thick takes twice as long. Opening to the middle and halving each time is logarithmic — a dictionary twice as thick costs one extra flip.

Explained

Checking a guest list of 1,000 names for duplicates by comparing every pair: about half a million comparisons. Instant.

The same code on 1,000,000 names: about 500 billion comparisons. In Python, that is most of a day.

Putting each name in a set as you go: a million steps. Under a second. Same answer, different growth.

The dictionary on the shelf

You need the word quokka in a 1,000-page paper dictionary.

Strategy A: start at page 1 and turn every page until you find it. Unlucky? 1,000 turns. A 2,000-page edition? 2,000 turns. The work grows in step with the book — that's linear.

Strategy B: open the middle, see you're in M, so throw away the first half. Open the middle of what's left. Each flip halves the pages. 1,000 pages → about 10 flips. 2,000 pages → about 11 flips. Doubling the book costs one extra flip — that's logarithmic.

Strategy B only works because the dictionary is sorted. Remember that price: fast lookups usually cost you some order you had to set up first.

Precisely

f(n) is O(g(n)) means: past some input size, f grows no faster than a constant times g. In practice you get there with three moves:

1. Count the steps as a function of n — 3n + 50 for one loop with a little setup.
2. Keep only the fastest-growing term — n² + 100n → n². At n = 10,000 the n² part is 99% of the work.
3. Drop constant factors — 3n → n. Constants depend on the machine and language; growth does not.

How code shapes map to classes:

• a fixed number of operations, no loop over the input → O(1)
• one pass over the input → O(n)
• a loop inside a loop over the same input → O(n²)
• a loop that halves the remaining work each time → O(log n)
• split in half, solve both halves, merge (merge sort) → O(n log n)
• try every subset → O(2ⁿ)

Space works the same way, but counts the extra memory you allocate: a few variables is O(1), a copy or a set of the input is O(n).

How many steps, roughly

n            log n    n        n log n      n²           2ⁿ
──────────────────────────────────────────────────────────────────
10           3        10       33           100          1,024
1,000        10       1,000    10,000       1,000,000    ≈10³⁰¹
1,000,000    20       10⁶      2×10⁷        10¹²         —

At ~10⁷ simple steps a second (a fair Python estimate), n = 1,000,000:

• O(log n) → microseconds
• O(n) → a tenth of a second
• O(n log n) → about 2 seconds
• O(n²) → about 28 hours

The jump from n log n to n² is where real programs go to die.

Linear search: check every box

12 sorted numbers, looking for 70. Linear search ignores the order and checks one box at a time: 11 checks to reach it. Double the array and the worst case doubles too — O(n) time, O(1) extra space.

Binary search: same array, halve the range

Same 12 numbers, same target. Check the middle (33): too small, discard the left half. Middle of the rest (50): too small again. Next middle: 70 — found in 3 checks. A million sorted items would take at most 20. O(log n) time, O(1) space — but only because the array is sorted.

Four functions, four classes

def first(items):                 # O(1) time, O(1) space
    return items[0]

def contains(items, x):           # O(n) time, O(1) space
    for v in items:
        if v == x:
            return True
    return False

def has_dup_slow(items):          # O(n²) time, O(1) space
    n = len(items)
    for i in range(n):
        for j in range(i + 1, n): # every pair once: n(n-1)/2
            if items[i] == items[j]:
                return True
    return False

def has_dup_fast(items):          # O(n) time, O(n) space
    seen = set()
    for v in items:
        if v in seen:             # set lookup: O(1) on average
            return True
        seen.add(v)
    return False

has_dup_fast buys speed by spending memory. That trade — more space for less time — is the most common optimisation you'll ever make.

Turning n into a time budget

Before writing code, an experienced engineer does this sum in their head: steps ≈ complexity at your n, then divide by ~10⁷ per second (Python) or ~10⁸–10⁹ (C, Java, Go).

| n | Fine | Too slow | | --- | --- | --- | | ≤ 20 | O(2ⁿ) — try every subset | | | ≤ 5,000 | O(n²) | O(2ⁿ) | | ≤ 10⁶ | O(n log n), O(n) | O(n²) | | ≥ 10⁹ | O(log n), O(1) per query | anything that reads everything per request |

This is why sorting (O(n log n)) is almost always affordable, and why "compare every pair" stops working somewhere around tens of thousands of items.

Words to know

In two minutes

• Big-O measures growth: what happens to the work when the input doubles. It ignores machine speed, constants and small terms (3n + 50 → O(n)).
• The ladder, fastest first: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ). Each rung is a different universe at n = 1,000,000.
• Linear search is O(n) time, O(1) space; binary search on a sorted array is O(log n) time, O(1) space — 20 checks for a million items.
• Loops in sequence add (O(n + m)); loops nested inside each other multiply (O(n × m), O(n²) on the same list).
• A loop that halves (or doubles) its counter each step is O(log n).
• Hidden loops count: x in some_list, list.index, slicing and sorted() all do work proportional to their size.
• Space complexity is the extra memory: a set of every item is O(n) space; a few counters are O(1). Trading space for time is the most common optimisation.
• Rule of thumb: Python does roughly 10⁷ simple steps a second. Multiply your complexity by n and you know whether it finishes in a blink or overnight.

Test yourself

for i in range(n):
    for j in range(n):
        total += i * j

i = 1
while i < n:
    i = i * 2

There are 10 questions, 3 puzzles and 6 recall cards for this lesson in the app — the recall cards come back on later days, just before you would forget.