Big-O notation, from first idea to production

I timed one function on two inputs. Comparing two 600-character strings took 39 milliseconds. Comparing two 5,000-character strings took 3.2 seconds. The input got about eight times longer and the run got more than eighty times slower. Nothing was wrong with the code. It did exactly the amount of work its shape promised: the work grows with the square of the length, so a little more input buys a lot more waiting.

Big-O notation is the language for that shape. It doesn’t tell you how many milliseconds something takes. It tells you what happens to the work when the input doubles, or grows a thousandfold, which is the question that matters when code that was fine in testing meets production data. The loop at the heart of that function runs in ezychat.io, the multi-tenant AI messaging product I’m the primary engineer of, and the production section shows how a single constant caps its input so the worst case stays at the 600-character timing above.

By the end you’ll be able to read the cost of a piece of code by looking at it, explain why x in my_list inside a loop is a bug waiting for data, use the precise vocabulary (Θ, amortized, worst case) without hand-waving, check your reasoning with a profiler, and spot the complexity bugs that matter most in backend systems: the ones in query plans and network round trips. Nothing is assumed beyond reading simple Python. If you already know what O(n log n) means, jump ahead with the level bar.

Beginner: counting steps instead of seconds

Why seconds are the wrong unit

The obvious way to ask “how fast is this code?” is to time it. Here’s a function that finds the largest number in a list, timed three times on a million numbers:

import time

def find_max(numbers):
    best = numbers[0]
    for x in numbers:
        if x > best:
            best = x
    return best

data = list(range(1_000_000))
for run in range(3):
    start = time.perf_counter()
    find_max(data)
    print(f"run {run + 1}: {(time.perf_counter() - start) * 1000:.1f} ms")
# run 1: 22.7 ms
# run 2: 19.1 ms
# run 3: 19.2 ms

Same code, same data, three different answers. Run it again and you get another three. On a faster laptop the numbers shrink; on a busy server they grow; in another language they can change tenfold. A time is a fact about one run on one machine. It’s useful, and later sections lean on it heavily, but it can’t answer the question you actually care about while writing code: what happens when the list is a hundred times bigger?

Count the steps

So count something that doesn’t depend on the machine: the number of basic steps. A step is any small piece of work that takes about the same time no matter how big the input is: comparing two numbers, adding them, reading numbers[i], assigning a variable. Here’s find_max again, counting its comparisons:

def find_max(numbers):
    steps = 0
    best = numbers[0]
    for x in numbers:
        steps += 1              # one comparison per item
        if x > best:
            best = x
    return best, steps

for n in (10, 1_000, 1_000_000):
    best, steps = find_max(list(range(n)))
    print(f"n = {n:>9,}   steps = {steps:>9,}")
# n =        10   steps =        10
# n =     1,000   steps =     1,000
# n = 1,000,000   steps = 1,000,000

The letter n is the size of the input, here the length of the list. The count is exactly n: one comparison per item. That’s a fact about the code, and it’s true on every machine. It also answers the hundred-times question immediately: a hundred times more numbers means a hundred times more comparisons, so roughly a hundred times longer.

That relationship, how the step count grows as n grows, is what Big-O describes. We say find_max is O(n), read “big O of n” or “order n”, and it means: the work grows in proportion to the input. Double the list, double the work.

Four shapes of growth

Most code you’ll write falls into a handful of shapes. Four of them cover almost everything at this level, and each has an everyday version.

• O(1), constant. Taking the top plate off a pile. The pile can be five plates or five hundred; it’s one step. In code: reading items[0], looking up prices["apple"] in a dictionary, adding two numbers.
• O(log n), logarithmic. Finding a name in a paper phone book by opening it in the middle, deciding which half the name is in, and repeating. Each step throws away half of what’s left, so even a huge book takes only a few steps. log n here means “how many times can you halve n before you reach 1?” For 16 that’s 4; for a million it’s about 20.
• O(n), linear. Reading every page of a book. Twice the pages, twice the reading.
• O(n²), quadratic. Everyone at a party shakes hands with everyone else. Six people make 15 handshakes; sixty people make 1,770. Add one guest and they shake hands with everybody already there. n² (“n squared”) means n × n.

Here are all four as Python, each counting its own steps:

def first_item(items):                 # constant: one step, whatever the size
    steps = 1                          # items[0] is a single lookup
    return steps

def total(items):                      # linear: one step per item
    steps = 0
    for x in items:
        steps += 1
    return steps

def has_duplicate(items):              # quadratic: every pair of items
    steps = 0
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            steps += 1
            if items[i] == items[j]:
                return steps
    return steps

def halvings(n):                       # logarithmic: halve until one is left
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps

print(f"{'n':>7} {'O(1)':>5} {'O(log n)':>9} {'O(n)':>7} {'O(n²)':>11}")
for n in (10, 100, 1_000, 10_000):
    items = list(range(n))             # all different: the worst case for has_duplicate
    print(f"{n:>7,} {first_item(items):>5} {halvings(n):>9} {total(items):>7,} {has_duplicate(items):>11,}")
#       n  O(1)  O(log n)    O(n)       O(n²)
#      10     1         3      10          45
#     100     1         6     100       4,950
#   1,000     1         9   1,000     499,500
#  10,000     1        13  10,000  49,995,000

Read the table down each column. Every row is ten times more data. The constant column doesn’t move. The logarithmic one adds about three steps per row. The linear one grows tenfold per row. The quadratic one grows a hundredfold per row, and at ten thousand items it’s doing fifty million comparisons to answer a yes-or-no question. (It’s n(n − 1)/2 rather than n², because each pair is checked once. Halving doesn’t change the shape, as the Intermediate section explains.)

That last column is why quadratic code is the first thing I look for when something is slow on real data and fine in tests. At 100 items it’s 4,950 steps, which is nothing. Every test passes. Then someone uploads a file with 100,000 rows.

Reading the cost of a loop

You rarely need to run code to know its shape. A few rules get you most of the way:

1. A simple statement is one step. Assignment, arithmetic, comparing two values, items[i], len(items), a dictionary lookup.
2. A loop costs the number of times it runs, times the cost of its body. for x in items: with a one-step body over n items is n steps: O(n).
3. A loop inside a loop multiplies. n outer runs, each doing n inner runs, is n × n: O(n²).
4. A loop that halves (or doubles) its variable runs about log n times. while n > 1: n //= 2 is O(log n).
5. Some single lines are loops in disguise. x in some_list checks items one by one. So do some_list.index(x), some_list.remove(x), sum(some_list), max(some_list) and sorted(some_list). A line that looks like one step can be n steps.

Rule 5 is the one that bites. The demo below has five snippets. Step through them and watch the counter; the grid fills one cell per counted step. Pay particular attention to the fourth, which looks like the single loop and behaves like the nested one.

1total = 02for x in items:3    total += x4print(total)

Things to try: run the nested loop at n = 4 and n = 8 and compare the counts (16 and 64: double n, four times the work). Run the halving loop at 8 and 16 (3 and 4: double n, one more step). Then run “Loop with in list” at 16 and look at the grid. Odd senders aren’t in the staff list, so each one walks the whole row before the answer is no. The last snippet builds a set first and does one lookup per sender: two rows of n instead of a square.

Space complexity: the scratch paper

Time isn’t the only cost. Code also uses memory, and space complexity describes how much extra memory it needs as n grows. Think of it as scratch paper: when you add up a column of numbers in your head, you keep one running total, however long the column. If instead you copied every number onto a new sheet, doubled, you’d need as much paper as the column itself.

The input itself doesn’t count; it’s already there before your function starts. Only the scratch paper does:

import tracemalloc

def total(items):                  # scratch paper: one running number
    s = 0
    for x in items:
        s += x
    return s

def doubled(items):                # scratch paper: a whole new list
    return [x * 2 for x in items]

def peak_extra_bytes(fn, items):
    tracemalloc.start()
    fn(items)
    peak = tracemalloc.get_traced_memory()[1]
    tracemalloc.stop()
    return peak

for n in (1_000, 100_000):
    items = list(range(n))         # the input itself is not counted
    print(f"n = {n:>7,}   total: {peak_extra_bytes(total, items):>9,} bytes"
          f"   doubled: {peak_extra_bytes(doubled, items):>9,} bytes")
# n =   1,000   total:       112 bytes   doubled:    36,720 bytes
# n = 100,000   total:       120 bytes   doubled: 3,996,848 bytes

tracemalloc records the most memory allocated while the function ran. total used about a hundred bytes at both sizes: O(1) space. doubled grew from 37 KB to 4 MB, a hundred times more for a hundred times more input: O(n) space. Neither is wrong. doubled has to return n numbers, so it can’t do better. But when a function builds a big intermediate list it doesn’t need (a list comprehension inside sum(...), say, where a generator would do), that’s memory you’re paying for nothing.

def a(items):
    return items[-1] * 2

def b(items):
    for i in range(0, len(items), 2):
        print(items[i])

def c(items):
    for x in items:
        for y in items[:10]:
            print(x, y)

def d(items):
    k = len(items)
    while k > 0:
        print(items[k - 1])
        k //= 3

PLANS = ["free", "starter", "pro", "enterprise"]

def plan_table(customers):
    rows = []
    for customer in customers:
        for plan in PLANS:
            rows.append((customer, plan, customer.plan == plan))
    return rows

Intermediate: the rules, and what Python’s built-ins cost

Drop the constants

Suppose a careful count of some function gives exactly 3n² + 100n + 500 steps. Big-O throws most of that away and says O(n²). Here’s why that’s reasonable rather than sloppy:

def exact_steps(n):
    return 3 * n**2 + 100 * n + 500     # what a careful count might give

for n in (10, 100, 1_000, 100_000):
    share = 3 * n**2 / exact_steps(n)
    print(f"n = {n:>7,}   steps = {exact_steps(n):>17,}   the n² term's share: {share:.2%}")
# n =      10   steps =             1,800   the n² term's share: 16.67%
# n =     100   steps =            40,500   the n² term's share: 74.07%
# n =   1,000   steps =         3,100,500   the n² term's share: 96.76%
# n = 100,000   steps =    30,010,000,500   the n² term's share: 99.97%

At small n the other terms matter. As n grows, the n² term takes over, and by a hundred thousand it’s 99.97% of the work. Big-O describes that large-n behavior, so it keeps only the dominant term (the one that grows fastest) and drops its constant factor (the 3). Two reasons for dropping the 3: it depends on what you call “a step” (is x > best one step or three machine instructions?), and it doesn’t change the answer to the scaling question. 3n² and n² both quadruple when n doubles.

Four rules follow, and they’re enough for most code reviews:

1. Drop constant factors. 5n is O(n). n / 2 is O(n). 1,000 is O(1).
2. Keep the dominant term. n² + n is O(n²). n + log n is O(n). The order to remember: 1, log n, n, n log n, n², 2ⁿ, each eventually dwarfing the one before.
3. Steps in sequence add; nested steps multiply. A loop over n followed by another loop over n is n + n = 2n, so O(n). A loop over n inside a loop over n is O(n²).
4. Different inputs get different letters. A function that walks a list of n orders and then a list of m products is O(n + m). One that walks the products for each order is O(n · m). Don’t collapse these into one letter unless you know the inputs are the same size. “O(n · m) where m is the catalogue size” tells a reviewer which input to worry about.

The ladder of growth rates

It’s one thing to know n² grows faster than n log n. It’s another to see by how much. Drag n below and watch the table. The time column turns step counts into something you can feel, at an assumed cost per step that you choose.

Two things to take away. First, the gap between classes dwarfs any constant factor. At a million items, an O(n log n) sort does about 20 million steps and an O(n²) one does a trillion: switching to a faster machine buys you a constant, switching algorithms buys you a factor of fifty thousand. Second, look at the “largest n in 1 second” column with the network cost selected. When each step is a round trip to another machine, even O(n) runs out of budget at two thousand items. Keep that in mind for the Expert section.

Where log n comes from: repeated halving

A logarithm sounds like school maths, but in code it almost always means one thing: the work is cut in half at every step. log₂ n is the number of times you can halve n before reaching 1. Doubling n adds just one more halving.

The classic example is binary search: finding a value in a sorted list by checking the middle, then searching only the half it must be in.

def binary_search(sorted_items, target):
    lo, hi, steps = 0, len(sorted_items) - 1, 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if sorted_items[mid] == target:
            return mid, steps
        if sorted_items[mid] < target:
            lo = mid + 1                # the target can only be in the right half
        else:
            hi = mid - 1                # ...or only in the left half
    return -1, steps

for n in (1_000, 1_000_000, 1_000_000_000):
    items = range(n)                    # a range acts like a sorted list without the memory
    _, steps = binary_search(items, -1) # missing: the longest search
    print(f"n = {n:>13,}   binary search: {steps:>2} steps   linear search: {n:>13,} steps")
# n =         1,000   binary search:  9 steps   linear search:         1,000 steps
# n =     1,000,000   binary search: 19 steps   linear search:     1,000,000 steps
# n = 1,000,000,000   binary search: 29 steps   linear search: 1,000,000,000 steps

A billion items, 29 comparisons. That’s the power of a logarithm, and it’s why sorted data and tree-shaped indexes are everywhere: a database finding one row among millions is doing a version of this. The catch is the word sorted. Binary search only works because the order tells you which half to throw away.

n log n, and why sorting costs it

O(n log n) is what you get when you do log n rounds of work and each round touches all n items. It’s the cost of every good general-purpose sorting algorithm, and it shows up whenever an algorithm sorts first and then does something linear.

Python’s sorted uses an algorithm called Timsort. You can count its comparisons by sorting objects that count every <:

import math, random

class Counted:
    """Wraps a number and counts every comparison sort makes."""
    comparisons = 0
    def __init__(self, v):
        self.v = v
    def __lt__(self, other):
        Counted.comparisons += 1
        return self.v < other.v

random.seed(1)
for n in (1_000, 10_000, 100_000):
    data = [Counted(random.random()) for _ in range(n)]
    Counted.comparisons = 0
    sorted(data)
    print(f"n = {n:>7,}   comparisons = {Counted.comparisons:>9,}   n·log2(n) = {n * math.log2(n):>11,.0f}")

data = [Counted(i) for i in range(100_000)]   # already sorted
Counted.comparisons = 0
sorted(data)
print(f"already sorted, n = 100,000: {Counted.comparisons:,} comparisons")
# n =   1,000   comparisons =     8,652   n·log2(n) =       9,966
# n =  10,000   comparisons =   120,216   n·log2(n) =     132,877
# n = 100,000   comparisons = 1,532,067   n·log2(n) =   1,660,964
# already sorted, n = 100,000: 99,999 comparisons

The counts track n·log₂ n closely. They can’t do much better: any sort that works by comparing pairs needs at least log₂(n!) comparisons in its worst case, because it has to tell apart all n! possible orderings of the input and each comparison has two outcomes. For 100,000 items log₂(n!) is about 1,516,704, so Timsort is within 1% of the theoretical floor on random data.

The last line is the interesting one. On already-sorted input Timsort makes n − 1 comparisons: it notices the data is one long ordered run and stops. So its cost depends on the input, which brings us to cases.

Best, average and worst case

The same function can do very different amounts of work on inputs of the same size. Linear search is the simplest example:

def linear_search(items, target):
    for steps, x in enumerate(items, start=1):
        if x == target:
            return steps
    return len(items)

items = list(range(1, 1_001))           # 1,000 items
print("best (first item): ", linear_search(items, 1))
print("worst (missing):   ", linear_search(items, 0))
average = sum(linear_search(items, t) for t in items) / len(items)
print("average over every target that exists:", average)
# best (first item):  1
# worst (missing):    1000
# average over every target that exists: 500.5

• The best case is the luckiest input of size n: one step.
• The worst case is the unluckiest: n steps, when the target is missing.
• The average case averages over some assumed mix of inputs: (n + 1) / 2 if every position is equally likely.

When people say an algorithm “is O(n)”, they almost always mean the worst case, and that’s the right default for backend work, because it’s what an unlucky or hostile input gets. The average case matters when you control the input distribution: hash maps are O(1) on average and O(n) in the worst case, and they’re still the right choice because the worst case needs an extraordinarily unlucky (or deliberately crafted) set of keys. The best case is almost never worth quoting. Every search algorithm has a best case of one step.

Recursion trees

Loops are easy to count. Recursive functions, which call themselves, need a different picture: a recursion tree, with one node per call and the total work being the sum over all nodes.

Here’s the textbook trap, the naive Fibonacci function, counting its own calls:

from functools import lru_cache

calls = 0
def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)      # two calls, each almost as big as this one

for n in (10, 20, 30):
    calls = 0
    fib(n)
    print(f"fib({n}): {calls:>9,} calls")

memo_calls = 0
@lru_cache(maxsize=None)
def fib_memo(n):
    global memo_calls
    memo_calls += 1
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

fib_memo(30)
print(f"fib_memo(30): {memo_calls} calls")
# fib(10):       177 calls
# fib(20):    21,891 calls
# fib(30): 2,692,537 calls
# fib_memo(30): 31 calls

Each call makes two more, so the tree roughly doubles in width at every level, and there are about n levels. Adding 10 to n multiplies the calls by about 123. That’s exponential growth, O(2ⁿ) as an upper bound, and it’s the shape that makes code unusable at modest sizes rather than slow at large ones. The memoized version caches each answer, so each fib_memo(k) is computed once: 31 calls for n = 30, O(n). Same recursion, different tree: caching collapses the repeated subtrees.

Divide-and-conquer algorithms make a different tree. Merge sort splits the list in half, sorts each half recursively, and merges the two sorted halves in one linear pass:

Read the tree by levels. The top call merges 8 items. The two calls below it merge 4 each: 8 in total. The four below those merge 2 each: 8 again. Every level costs n, and there are log₂ n levels before the pieces are single items. Total: n log n. That level-by-level sum is the general technique; the Advanced section turns it into a formula.

Recursion has a space cost too. Each call waiting for its children keeps a frame on the call stack, so the extra memory is the depth of the tree: O(n) for fib, O(log n) of stack for merge sort (plus O(n) for the merged lists). Python’s default recursion limit is 1,000 frames, which is why deep recursion on large inputs fails with RecursionError long before it runs out of memory.

What Python’s built-ins cost

Rule 5 from the Beginner section says some lines are loops in disguise. Here’s the list for Python’s core types, with measurements so you can see the shapes. The column to read is how each row changes when n grows ten times:

import timeit

def per_call(stmt, setup, n, number):
    """Best of 5 runs, in microseconds per call."""
    t = min(timeit.repeat(stmt, setup, repeat=5, number=number, globals={"n": n}))
    return t / number * 1e6

cases = [
    ("lst.append(0); lst.pop()",       "lst = list(range(n))"),
    ("lst.insert(0, 0); lst.pop(0)",   "lst = list(range(n))"),
    ("-1 in lst",                      "lst = list(range(n))"),
    ("-1 in st",                       "st = set(range(n))"),
    ("d[n // 2]",                      "d = dict.fromkeys(range(n))"),
    ("lst[: n // 2]",                  "lst = list(range(n))"),
    ("sorted(data)",                   "import random; random.seed(0); data = [random.random() for _ in range(n)]"),
    ("len(lst)",                       "lst = list(range(n))"),
]
cheap = {"lst.append(0); lst.pop()", "-1 in st", "d[n // 2]", "len(lst)"}
print(f"{'operation':<30} {'n = 10,000':>12} {'n = 100,000':>12}")
for stmt, setup in cases:
    number = 100_000 if stmt in cheap else 20
    small = per_call(stmt, setup, 10_000, number)
    big = per_call(stmt, setup, 100_000, number)
    print(f"{stmt:<30} {small:>10.3f}µs {big:>10.3f}µs")
# operation                        n = 10,000  n = 100,000
# lst.append(0); lst.pop()            0.017µs      0.017µs
# lst.insert(0, 0); lst.pop(0)        5.635µs     62.612µs
# -1 in lst                          52.815µs    538.596µs
# -1 in st                            0.011µs      0.011µs
# d[n // 2]                           0.034µs      0.034µs
# lst[: n // 2]                       9.606µs    124.598µs
# sorted(data)                      849.617µs  10674.598µs
# len(lst)                            0.020µs      0.020µs

Measured on my laptop with Python 3.13. The O(1) rows don’t move. The O(n) rows grow about ten times. sorted grows about 12.6 times, which is ten times n plus the extra log factor. The table that goes with it, for reference (the “average” for sets and dicts is the hash table caveat from above):

The Python wiki’s TimeComplexity page has the full list, including the worst cases.

One row is missing from that table because it has a twist: building a string with += in a loop. Each s += "x" makes a new string and copies the old one into it, so n appends should copy 1 + 2 + … + n characters: O(n²). Measure it:

import time

def build_str(n):
    s = ""
    for _ in range(n):
        s += "x"                    # CPython often resizes s in place here
    return s

def build_str_shared(n):
    s = ""
    keep = []
    for _ in range(n):
        keep.append(s)              # a second reference to s blocks the in-place trick
        s += "x"
        keep.pop()
    return s

def build_bytes(n):
    b = b""
    for _ in range(n):
        b += b"x"                   # bytes never get the trick: every += copies
    return b

def build_join(n):
    return "".join("x" for _ in range(n))

for fn in (build_str, build_str_shared, build_bytes, build_join):
    row = []
    for n in (50_000, 100_000, 200_000):
        start = time.perf_counter()
        fn(n)
        row.append(f"{(time.perf_counter() - start) * 1000:8.1f} ms")
    print(f"{fn.__name__:<17}", *row)
# build_str              2.3 ms      4.5 ms      9.1 ms
# build_str_shared      34.4 ms    235.1 ms    705.4 ms
# build_bytes           38.0 ms    289.9 ms    755.4 ms
# build_join             2.0 ms      3.1 ms      6.1 ms

The plain version is linear. CPython has an optimization: when nothing else refers to the string, s += t can grow it in place instead of copying. But it’s fragile. Keep one other reference to s (here, a list holding it for a moment) and the copies come back, quadratic again. Bytes never get it at all. PEP 8, Python’s style guide, says not to rely on this optimization, because other Python implementations don’t have it, and you’ve just seen how easily CPython loses it. Use "".join(parts) or io.StringIO when you build a string from many pieces.

Practice: costing real code

These come up in code review constantly. Work out each answer before opening the solution.

def above_average(prices):
    total = 0
    for p in prices:
        total += p
    mean = total / len(prices)
    above = 0
    for p in prices:
        if p > mean:
            above += 1
    return above

def above_average(prices):
    steps = 0
    total = 0
    for p in prices:                # pass 1: n steps
        total += p
        steps += 1
    mean = total / len(prices)
    above = 0
    for p in prices:                # pass 2: another n steps
        if p > mean:
            above += 1
        steps += 1
    return above, steps

for n in (1_000, 1_000_000):
    above, steps = above_average(list(range(n)))
    print(f"n = {n:>9,}: {steps:>9,} steps")
# n =     1,000:     2,000 steps
# n = 1,000,000: 2,000,000 steps

def returning(today, last_month):
    return [c for c in today if c in last_month]

import time

def returning_slow(today, last_month):
    return [c for c in today if c in last_month]          # list: a hidden loop

def returning_fast(today, last_month):
    seen = set(last_month)                                 # built once: m steps
    return [c for c in today if c in seen]                 # n jumps

last_month = [f"user{i}@example.com" for i in range(50_000)]
today = [f"user{i}@example.com" for i in range(45_000, 50_000)] + \
        [f"new{i}@example.com" for i in range(5_000)]      # 10,000 senders, half returning

for fn in (returning_slow, returning_fast):
    start = time.perf_counter()
    result = fn(today, last_month)
    print(f"{fn.__name__}: {len(result):,} returning, {(time.perf_counter() - start) * 1000:,.1f} ms")
# returning_slow: 5,000 returning, 3,930.7 ms
# returning_fast: 5,000 returning, 4.2 ms

import tracemalloc

def grid_bytes(n):
    tracemalloc.start()
    grid = [[0] * n for _ in range(n)]
    size = tracemalloc.get_traced_memory()[0]
    tracemalloc.stop()
    return size

for n in (500, 1_000, 2_000):
    print(f"n = {n:>5,}: {grid_bytes(n) / 1e6:6.1f} MB")

trap = [[0] * 3] * 3           # three references to ONE row
trap[0][0] = 1
print(trap)
# n =   500:    2.0 MB
# n = 1,000:    8.1 MB
# n = 2,000:   32.1 MB
# [[1, 0, 0], [1, 0, 0], [1, 0, 0]]

def split(n):
    if n <= 1:
        return
    split(n // 2)
    split(n // 2)

calls = 0
def split(n):
    global calls
    calls += 1
    if n <= 1:
        return
    split(n // 2)
    split(n // 2)

for n in (1_024, 4_096, 16_384):
    calls = 0
    split(n)
    print(f"n = {n:>6,}: {calls:>6,} calls")
# n =  1,024:  2,047 calls
# n =  4,096:  8,191 calls
# n = 16,384: 32,767 calls

Advanced: precise notation, amortized cost, and what Big-O hides

O, Ω and Θ: upper, lower and tight bounds

So far “O(n)” has meant “grows like n”. The precise definition is narrower, and the gap explains some confusing conversations.

f(n) is O(g(n)) if there are constants c and n₀ such that f(n) ≤ c · g(n) for every n ≥ n₀. In words: past some size, f never grows faster than a constant times g. It’s an upper bound. Take f(n) = 3n + 5:

f = lambda n: 3 * n + 5                       # an exact step count

print(all(3 * n <= f(n) <= 4 * n for n in range(5, 1_000_000)))   # squeezed between 3n and 4n
print([n for n in range(1, 10) if f(n) > 4 * n])                  # the small n where 4n isn't enough yet
# True
# [1, 2, 3, 4]

With c = 4 and n₀ = 5, f(n) ≤ 4n holds from 5 onwards, so 3n + 5 is O(n). (A check over a million values isn’t a proof, but the algebra is one line: 3n + 5 ≤ 4n exactly when n ≥ 5.) The small values where it fails are the reason for n₀: Big-O only promises anything for large n.

Two more symbols complete the set:

• Ω(g(n)), “big omega”, is the matching lower bound: f(n) ≥ c · g(n) past some n₀. 3n + 5 is Ω(n), because it’s at least 3n.
• Θ(g(n)), “big theta”, means both at once: a tight bound. 3n + 5 is Θ(n).

Here’s the subtlety. Because O is only an upper bound, 3n + 5 is also O(n²), and O(2ⁿ). Those statements are true and useless. When engineers say “this is O(n)”, they nearly always mean Θ(n): it grows like n, no faster and no slower. That’s fine in conversation. It matters when you read papers or library docs, where O(n) genuinely means “at most”.

The second subtlety: O, Ω and Θ are about functions, not about best and worst cases. You can state a tight bound for each case separately. Linear search is Θ(1) in its best case and Θ(n) in its worst. Saying “Big-O is the worst case and Big-Omega is the best case” is a common mix-up; it’s two separate axes.

Amortized analysis: why append is O(1)

A Python list is a dynamic array: a block of memory with room for some number of pointers, its capacity. Appending puts the new item in the next free slot: one step. When the block is full, the list allocates a bigger block and copies every existing item across. That append costs n steps. So how can the table above call append O(1)?

Because the expensive appends are rare, and they get rarer as the list grows. If the array doubles each time it fills, the copies happen at sizes 1, 2, 4, 8, … and add up to less than n in total.

That’s amortized cost: the total cost of a long sequence of operations, divided by the number of operations. A single append can be expensive; the average over any sequence of appends is a constant. The usual way to prove it is the accounting argument. Charge every append 3 units instead of 1. One pays for placing the item; two go into savings. When the array of size k fills up and has to copy k items, the k/2 appends since the last resize have saved exactly k units. The bank never goes negative, so 3 units per append always covers everything.

The growth has to be by a factor, though. Here’s doubling against growing by a fixed 100 slots:

def copies(n, grow):
    capacity, total = 1, 0
    for size in range(1, n + 1):
        if size > capacity:
            total += size - 1           # move everything into the new block
            capacity = grow(capacity)
    return total

for n in (10_000, 100_000, 1_000_000):
    doubling = copies(n, lambda c: c * 2)
    plus_100 = copies(n, lambda c: c + 100)
    print(f"n = {n:>9,}   double: {doubling / n:4.2f} copies per append   "
          f"+100 slots: {plus_100 / n:>7,.1f} copies per append")
# n =    10,000   double: 1.64 copies per append   +100 slots:    49.5 copies per append
# n =   100,000   double: 1.31 copies per append   +100 slots:   499.5 copies per append
# n = 1,000,000   double: 1.05 copies per append   +100 slots: 4,999.5 copies per append

With a fixed increment, the copies per append grow with n: n appends cost O(n²) in total. With a factor, they stay constant.

CPython’s list doesn’t actually double. You can watch its capacity through sys.getsizeof (56 bytes of header plus 8 per slot on a 64-bit build):

import sys

lst, last, grows = [], sys.getsizeof([]), []
for i in range(1, 1_000_001):
    lst.append(i)
    size = sys.getsizeof(lst)
    if size != last:
        grows.append((i, (size - 56) // 8))   # (length when it grew, new capacity in slots)
        last = size

print("first growths (length -> capacity):", grows[:8])
print("growths to reach 1,000,000 items:", len(grows))
copied = sum(length - 1 for length, _ in grows)  # items moved by each reallocation, at worst
print(f"items copied in total, at most: {copied:,}  ({copied / 1_000_000:.2f} per append)")
# first growths (length -> capacity): [(1, 4), (5, 8), (9, 16), (17, 24), (25, 32), (33, 40), (41, 52), (53, 64)]
# growths to reach 1,000,000 items: 86
# items copied in total, at most: 8,445,096  (8.45 per append)

It grows by about an eighth each time (the CPython source computes the new size as roughly n + n/8, plus a little, rounded). A smaller factor wastes less memory and does more copies: at most about 8.5 per append here, and fewer in practice, because the memory allocator can often extend a block in place without copying. It’s still a constant, so append is still amortized O(1). The factor is a space-time trade, and every language picks its own.

Amortized is a promise about totals, not about each operation. The append that triggers a resize of a 100-million-item list really does copy 100 million pointers, all at once. For a batch job that’s irrelevant. For a latency-sensitive service holding a giant in-memory structure, it’s a pause someone will see in a p99 graph. Systems that care, like Redis’s incremental rehashing, spread the move over many later operations so no single one pays.

import time
from collections import deque

def drain_list(n):
    q = list(range(n))
    while q:
        q.pop(0)                    # every pop shifts everything left by one

def drain_deque(n):
    q = deque(range(n))
    while q:
        q.popleft()                 # a deque just moves its start pointer

for fn in (drain_list, drain_deque):
    row = []
    for n in (50_000, 100_000, 200_000):
        start = time.perf_counter()
        fn(n)
        row.append(f"{(time.perf_counter() - start) * 1000:7.1f} ms")
    print(f"{fn.__name__:<12}", *row)
# drain_list     189.9 ms   773.9 ms  3246.3 ms
# drain_deque      1.7 ms     3.4 ms     7.1 ms

Divide and conquer: a formula for recursive costs

Merge sort, binary search and many tree algorithms share a shape: split the problem into a subproblems, each 1/b the size, solve them recursively, and spend f(n) splitting and combining. Their cost satisfies a recurrence:

T(n) = a · T(n / b) + f(n)

The Master theorem solves recurrences of this shape by comparing f(n) with n^(log_b a), which is the number of leaves in the recursion tree:

1. The leaves dominate. If f(n) grows polynomially slower than n^(log_b a), then T(n) = Θ(n^(log_b a)). Most of the work is at the bottom of the tree.
2. Every level costs the same. If f(n) is Θ(n^(log_b a)), then T(n) = Θ(n^(log_b a) · log n). That’s the merge sort tree: n per level, log n levels.
3. The root dominates. If f(n) grows polynomially faster (and a mild regularity condition holds), then T(n) = Θ(f(n)). The top call’s own work outweighs everything below it.

You can check the cases by computing T exactly and doubling n. If T grows like n^k, doubling n multiplies T by 2^k:

from functools import lru_cache

@lru_cache(maxsize=None)
def work(n, a, b, combine):
    """T(n) = a·T(n/b) + combine(n), with T(1) = 1, counted exactly."""
    if n <= 1:
        return 1
    return a * work(n // b, a, b, combine) + combine(n)

one = lambda n: 1
linear = lambda n: n

recurrences = [
    ("binary search   a=1 b=2 f=1", 1, 2, one),
    ("tree walk       a=2 b=2 f=1", 2, 2, one),
    ("merge sort      a=2 b=2 f=n", 2, 2, linear),
    ("karatsuba       a=3 b=2 f=n", 3, 2, linear),
]
for name, a, b, f in recurrences:
    t1, t2 = work(2**16, a, b, f), work(2**17, a, b, f)
    print(f"{name}   T(2^17) / T(2^16) = {t2 / t1:.3f}")
# binary search   a=1 b=2 f=1   T(2^17) / T(2^16) = 1.059
# tree walk       a=2 b=2 f=1   T(2^17) / T(2^16) = 2.000
# merge sort      a=2 b=2 f=n   T(2^17) / T(2^16) = 2.118
# karatsuba       a=3 b=2 f=n   T(2^17) / T(2^16) = 3.001

• Binary search, a = 1, b = 2, f = 1: n^(log₂ 1) = n⁰ = 1, the same as f, so case 2 gives Θ(log n). Doubling n adds one level: 18/17 ≈ 1.059.
• Tree walk (visit both halves, constant work per node, the split exercise): n^(log₂ 2) = n beats f = 1, so case 1 gives Θ(n). Exactly 2.000.
• Merge sort: n^(log₂ 2) = n equals f = n, case 2, Θ(n log n). Slightly more than 2 per doubling: the log factor.
• Karatsuba multiplication splits two big numbers into halves and gets away with 3 half-size multiplications instead of 4: n^(log₂ 3) ≈ n^1.585 beats f = n, case 1. Doubling n triples the work. Python’s own int multiplication switches to Karatsuba for very large numbers, for exactly this reason.

The theorem doesn’t cover everything. Uneven splits (T(n) = T(n − 1) + n, which is Θ(n²)) and naive Fibonacci (T(n) = T(n − 1) + T(n − 2)) aren’t of the form a · T(n / b). For those, go back to drawing the tree and summing the levels.

Hidden constants: memory, objects and locality

Big-O says two O(n) algorithms are the same. They can easily differ by ten times, and at this level the reasons are worth knowing, because they explain measurements that otherwise look like noise.

Python objects are big. A list doesn’t hold numbers; it holds pointers to integer objects that live elsewhere in memory, each with its own header:

import sys, tracemalloc
from array import array

n = 1_000_000
print("one int object:", sys.getsizeof(10**6), "bytes")

tracemalloc.start()
as_list = list(range(10**6, 10**6 + n))       # a million int objects + a million pointers
print(f"list of {n:,} ints:  {tracemalloc.get_traced_memory()[0] / 1e6:5.1f} MB")
tracemalloc.stop()

tracemalloc.start()
as_array = array("q", range(10**6, 10**6 + n))  # raw 8-byte integers, side by side
print(f"array of {n:,} ints: {tracemalloc.get_traced_memory()[0] / 1e6:5.1f} MB")
tracemalloc.stop()
# one int object: 28 bytes
# list of 1,000,000 ints:   40.0 MB
# array of 1,000,000 ints:   8.2 MB

Both are O(n) space. One is five times the other. When “it’s only O(n) memory” meets a hundred million rows, that factor of five decides whether the job fits on the machine.

Memory order matters. A CPU doesn’t read memory one byte at a time. It fetches a cache line (typically 64 or 128 bytes) into a small, fast cache, and it guesses which line you’ll want next. Reading memory in order is fast because the next item is usually already in the cache. Jumping around means a trip to main memory, which Jeff Dean’s latency table puts at about 100 ns, two hundred times slower than an L1 cache hit. Here’s the same O(n) sum done three ways:

import random, timeit

class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, next=None):
        self.value, self.next = value, next

def sum_linked(head):
    total, node = 0, head
    while node is not None:
        total += node.value
        node = node.next
    return total

n = 1_000_000
values = list(range(10**6, 10**6 + n))
head = None
for v in reversed(values):
    head = Node(v, head)

shuffled = values[:]                # the same int objects...
random.seed(0)
random.shuffle(shuffled)            # ...visited in a random memory order

def best_ms(fn):
    return min(timeit.repeat(fn, number=1, repeat=5)) * 1000

print(f"sum(list), objects in memory order:    {best_ms(lambda: sum(values)):6.1f} ms")
print(f"sum(list), same objects, shuffled:     {best_ms(lambda: sum(shuffled)):6.1f} ms")
print(f"walk a linked list in a Python loop:   {best_ms(lambda: sum_linked(head)):6.1f} ms")
# sum(list), objects in memory order:       2.9 ms
# sum(list), same objects, shuffled:       12.5 ms
# walk a linked list in a Python loop:     26.9 ms

The first two lines add up the same million objects. The only difference is the order the list visits them in. In creation order they sit roughly side by side in memory; shuffled, every step is a jump, and the sum is four times slower. The linked list pays twice: a jump per node and an interpreted loop per step. This is the practical case for arrays over linked lists in almost every language, even for operations where the linked list has the better Big-O. Inserting into the middle of an array is O(n), but it’s one fast contiguous memory move; walking a linked list to the insertion point is also O(n), with a cache miss per step.

Checking reality: timeit, cProfile and a doubling test

Analysis tells you what should happen. Measurement tells you what does. Three tools cover nearly everything.

timeit runs a small statement many times and reports the best time, which filters out noise from other processes. From the shell:

$ python3 -m timeit -s "lst = list(range(100_000))" "100_000 in lst"
500 loops, best of 5: 549 usec per loop
$ python3 -m timeit -s "st = set(range(100_000))" "100_000 in st"
20000000 loops, best of 5: 11 nsec per loop

A doubling test turns timings into a complexity estimate. If code is O(n^k), doubling n multiplies its time by 2^k, so log₂ of the ratio estimates k. This is the most useful ten lines in this article for real work, because you can point it at any function without reading it:

import math, time

def growth_exponent(fn, make_input, sizes=(2_000, 4_000, 8_000)):
    """Time fn at doubling sizes. log2(t(2n) / t(n)) estimates k in O(n^k)."""
    times = []
    for n in sizes:
        data = make_input(n)
        best = float("inf")
        for _ in range(3):                    # best of three: less noise
            start = time.perf_counter()
            fn(data)
            best = min(best, time.perf_counter() - start)
        times.append(best)
    for (n, t0), t1 in zip(zip(sizes, times), times[1:]):
        print(f"  {n:>6,} -> {2 * n:>6,}: x{t1 / t0:4.1f}   exponent ≈ {math.log2(t1 / t0):.2f}")

def dedupe_list(items):             # `in` on a list inside a loop
    out = []
    for x in items:
        if x not in out:
            out.append(x)
    return out

def dedupe_dict(items):
    return list(dict.fromkeys(items))

print("dedupe_list");  growth_exponent(dedupe_list, lambda n: list(range(n)))
print("dedupe_dict");  growth_exponent(dedupe_dict, lambda n: list(range(n)), sizes=(200_000, 400_000, 800_000))
# dedupe_list
#    2,000 ->  4,000: x 4.0   exponent ≈ 2.00
#    4,000 ->  8,000: x 4.0   exponent ≈ 2.00
# dedupe_dict
#   200,000 -> 400,000: x 1.9   exponent ≈ 0.90
#   400,000 -> 800,000: x 2.1   exponent ≈ 1.08

Quadratic and linear, measured rather than argued. Use sizes big enough that each run takes milliseconds, or timer noise swamps the ratio.

cProfile answers a different question: where is the time going in a bigger program? It counts every function call and the time spent in each. Here’s a small nightly report with a hidden quadratic step:

import cProfile, pstats, random

def load_orders(n):
    random.seed(0)
    return [{"id": i, "customer": random.randrange(n // 4)} for i in range(n)]

def unique_customers(orders):
    seen = []
    for order in orders:
        if order["customer"] not in seen:     # looks like one step
            seen.append(order["customer"])
    return seen

def format_report(customers):
    return "\n".join(f"customer {c}" for c in customers)

def nightly_report(n):
    orders = load_orders(n)
    customers = unique_customers(orders)
    return format_report(customers)

cProfile.run("nightly_report(40_000)", "report.prof")
pstats.Stats("report.prof").sort_stats("cumulative").print_stats(5)

The output, with file paths trimmed:

         245352 function calls in 1.170 seconds

   Ordered by: cumulative time
   List reduced from 18 to 5 due to restriction <5>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    1.170    1.170 {built-in method builtins.exec}
        1    0.002    0.002    1.170    1.170 <string>:1(<module>)
        1    0.000    0.000    1.168    1.168 report.py:17(nightly_report)
        1    1.119    1.119    1.121    1.121 report.py:7(unique_customers)
        1    0.009    0.009    0.045    0.045 report.py:3(load_orders)

unique_customers has 1.119 seconds of tottime, time spent in its own code rather than in functions it calls, out of 1.170. The in on a list doesn’t show up as a separate call, because it’s a single bytecode operation, which is exactly why it’s easy to miss. The profiler points you at the function; reading the function with the rules from this article finds the line. Replacing seen with a set is the whole fix.

Expert: when Big-O misleads, and where the real costs live

Everything so far treats a step as a step. Real systems have steps that differ by a factor of a million, and inputs that are often small. This section is about the judgment calls.

At small n, constants win

Insertion sort is O(n²). Merge sort is O(n log n). Here they are in pure Python on small lists:

import random, timeit

def insertion_sort(a):              # O(n²), but each step is tiny
    a = a[:]
    for i in range(1, len(a)):
        x, j = a[i], i - 1
        while j >= 0 and a[j] > x:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = x
    return a

def merge_sort(a):                  # O(n log n), but each step does more
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

random.seed(0)
for n in (8, 16, 32, 64, 128, 512):
    data = [random.random() for _ in range(n)]
    ins = min(timeit.repeat(lambda: insertion_sort(data), number=200, repeat=5)) / 200
    mrg = min(timeit.repeat(lambda: merge_sort(data), number=200, repeat=5)) / 200
    winner = "insertion" if ins < mrg else "merge"
    print(f"n = {n:>3}   insertion {ins * 1e6:8.1f} µs   merge {mrg * 1e6:8.1f} µs   faster: {winner}")
# n =   8   insertion      1.5 µs   merge      3.7 µs   faster: insertion
# n =  16   insertion      3.8 µs   merge      9.0 µs   faster: insertion
# n =  32   insertion     15.9 µs   merge     21.4 µs   faster: insertion
# n =  64   insertion     59.2 µs   merge     47.0 µs   faster: merge
# n = 128   insertion    200.8 µs   merge    105.5 µs   faster: merge
# n = 512   insertion   3899.3 µs   merge    516.6 µs   faster: merge

Below somewhere between 32 and 64 items, the “worse” algorithm wins, because it does no recursion, no slicing and no list building. Above that, the shapes take over, and by 512 items insertion sort is more than seven times slower. This isn’t a curiosity: it’s exactly how production sorts are built. CPython’s Timsort sorts short runs with binary insertion sort, and its design notes (listsort.txt in the CPython source) choose a minimum run length between 32 and 64. Other standard libraries use a similar small-input cutoff. Big-O picks the algorithm for large inputs; measurement picks the cutoff.

The practical rule I use: if n is bounded and small, write the clearest code and move on. A nested loop over a user’s 5 saved addresses is fine. A nested loop over “all rows in the table” is not, even if the table is small today.

Constant factors you can’t ignore

Two O(n) ways to add a million numbers:

import timeit

data = list(range(1_000_000))

def loop_sum(items):
    total = 0
    for x in items:                 # every step runs through the interpreter
        total += x
    return total

loop = min(timeit.repeat(lambda: loop_sum(data), number=5, repeat=5)) / 5
builtin = min(timeit.repeat(lambda: sum(data), number=5, repeat=5)) / 5
print(f"Python loop: {loop * 1000:5.1f} ms   sum(): {builtin * 1000:4.1f} ms   both O(n), ratio {loop / builtin:.1f}x")
print(f"per item: loop {loop / len(data) * 1e9:.0f} ns, sum() {builtin / len(data) * 1e9:.1f} ns")
# Python loop:  19.3 ms   sum():  2.9 ms   both O(n), ratio 6.8x
# per item: loop 19 ns, sum() 2.9 ns

The built-in runs its loop in C; the Python loop interprets several bytecodes per item. That 19 ns per step, rounded to 20, is the growth explorer’s “Python loop step” figure. In Python specifically, “push the loop into a built-in” (sum, max, sorted, set operations, str.join, comprehensions, NumPy) is often worth a large constant factor (6.8 times for sum here). It never changes the shape, though: a vectorized O(n²) is still O(n²), just with a later cliff.

I/O versus CPU

The biggest constants aren’t in the CPU at all. Here’s a dictionary lookup against a round trip over a TCP connection to another thread on the same machine, with no network card involved:

import socket, threading, time, timeit

def echo_server(sock):
    conn, _ = sock.accept()
    with conn:
        while data := conn.recv(64):
            conn.sendall(data)

server = socket.create_server(("127.0.0.1", 0))
threading.Thread(target=echo_server, args=(server,), daemon=True).start()
client = socket.create_connection(server.getsockname())
client.setsockopt(socket.IPPROTO_TCP, socket.TCP_NODELAY, 1)

def round_trip():
    client.sendall(b"ping")
    client.recv(64)

n = 5_000
start = time.perf_counter()
for _ in range(n):
    round_trip()
rtt = (time.perf_counter() - start) / n

d = {i: i for i in range(1_000)}
lookup = min(timeit.repeat("d[500]", globals={"d": d}, number=1_000_000, repeat=5)) / 1_000_000

print(f"dict lookup:                  {lookup * 1e9:8.0f} ns")
print(f"TCP round trip on localhost:  {rtt * 1e9:8.0f} ns  ({rtt / lookup:,.0f} dict lookups)")
# dict lookup:                        19 ns
# TCP round trip on localhost:     22612 ns  (1,186 dict lookups)

One local round trip costs about as much as twelve hundred dictionary lookups. Across a real network it’s worse: Jeff Dean’s table puts a round trip inside one datacenter at 500 µs, and California to the Netherlands and back at 150 ms. Disk reads sit in between.

This changes how to count. In a backend request, the unit of cost is usually the round trip, not the CPU step. An algorithm that does O(n) CPU work and O(1) database queries will beat one that does O(1) CPU work and O(n) queries for every n that matters. Big-O still works; you just have to count the right thing.

Database query plans: a scan or an index

A SQL query doesn’t say how to find the rows. The database’s planner decides, and the two basic choices have the shapes you now know:

• A sequential scan reads every row of the table and keeps the ones that match: O(n) in the table’s size, however few rows you want.
• An index is a separate structure, usually a B-tree, that keeps a column’s values sorted with pointers back to the rows. Finding a value is a walk down the tree, O(log n), and because each tree node is a disk page holding hundreds of keys, a table of millions of rows is typically only three or four levels deep. Reading k matching rows after that is O(log n + k).

Indexes also sort. If an index already holds rows in the order a query wants, the database can read them in that order and stop after the first k. If not, it has to collect every matching row and sort it: O(m log m) for m matches, and when they don’t fit in memory, a sort that spills to disk.

You can watch all three plans with SQLite, which ships with Python. A million conversations across 50 organizations; the query asks for one organization’s 50 newest:

import random, sqlite3, time

db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE conversations (id INTEGER PRIMARY KEY, org_id INT, status TEXT, last_msg REAL)")
random.seed(0)
rows = ((i, random.randrange(50), random.choice(["open", "closed"]), random.random())
        for i in range(1_000_000))
db.executemany("INSERT INTO conversations VALUES (?, ?, ?, ?)", rows)

QUERY = "SELECT id FROM conversations WHERE org_id = 7 ORDER BY last_msg DESC LIMIT 50"

def show(label):
    plan = [row[-1] for row in db.execute("EXPLAIN QUERY PLAN " + QUERY)]
    start = time.perf_counter()
    for _ in range(20):
        db.execute(QUERY).fetchall()
    ms = (time.perf_counter() - start) / 20 * 1000
    print(f"{label:<38} {ms:7.2f} ms   plan: {plan}")

show("no index")
db.execute("CREATE INDEX ix_org_status_last ON conversations (org_id, status, last_msg)")
show("index on (org_id, status, last_msg)")
db.execute("CREATE INDEX ix_org_last ON conversations (org_id, last_msg)")
show("index on (org_id, last_msg)")
# no index                                 26.70 ms   plan: ['SCAN conversations', 'USE TEMP B-TREE FOR ORDER BY']
# index on (org_id, status, last_msg)       2.17 ms   plan: ['SEARCH conversations USING COVERING INDEX ix_org_status_last (org_id=?)', 'USE TEMP B-TREE FOR ORDER BY']
# index on (org_id, last_msg)               0.01 ms   plan: ['SEARCH conversations USING COVERING INDEX ix_org_last (org_id=?)']

Read the plans:

1. No index: SCAN the whole million-row table, then build a temporary B-tree to sort the matches. O(n) plus a sort.
2. Index on (org_id, status, last_msg): SEARCH jumps straight to organization 7, about 20,000 rows. But inside the index those rows are ordered by status first, then time, so “newest overall” is spread across two sorted runs. The database still has to read all of the organization’s rows and sort them: USE TEMP B-TREE FOR ORDER BY.
3. Index on (org_id, last_msg): organization 7’s rows are already newest first. Read 50 and stop. No sort, and it’s two orders of magnitude faster than plan 2.

Plan 2 is the one to remember, because it looks fixed. There is an index, the query does use it, and it’s still doing work proportional to the tenant’s whole history on every request. This exact shape cost real time in ezychat’s inbox; the production section has the numbers. In PostgreSQL, EXPLAIN (ANALYZE, BUFFERS) shows the same story with actual row counts and whether the sort spilled to disk.

The N+1 query problem is a complexity bug

Here’s the most common performance bug in web backends. A page lists posts, and each post shows the accounts it was published to. The obvious code loads the posts with one query, then, for each post, loads its targets:

That’s 1 query for the list plus N queries for the details: N + 1. Each query might be fast, a millisecond on an indexed column, so the page feels fine in development with five posts. The cost is O(N) round trips, and round trips are the expensive unit. Here it is with a simulated 0.5 ms network delay per query:

import sqlite3, time

db = sqlite3.connect(":memory:")
db.executescript("""
    CREATE TABLE posts   (id INTEGER PRIMARY KEY, body TEXT);
    CREATE TABLE targets (id INTEGER PRIMARY KEY, post_id INT, account TEXT);
    CREATE INDEX ix_targets_post ON targets (post_id);
""")
db.executemany("INSERT INTO posts VALUES (?, ?)", ((i, f"post {i}") for i in range(50)))
db.executemany("INSERT INTO targets (post_id, account) VALUES (?, ?)",
               ((i, acct) for i in range(50) for acct in ("ig", "fb")))

ROUND_TRIP = 0.0005                  # pretend each query crosses a network: 0.5 ms
queries = 0
def query(sql, params=()):
    global queries
    queries += 1
    time.sleep(ROUND_TRIP)
    return db.execute(sql, params).fetchall()

def n_plus_one():
    posts = query("SELECT id, body FROM posts")
    return {pid: query("SELECT account FROM targets WHERE post_id = ?", (pid,)) for pid, _ in posts}

def batched():
    posts = query("SELECT id, body FROM posts")
    ids = [pid for pid, _ in posts]
    marks = ",".join("?" * len(ids))
    by_post = {pid: [] for pid in ids}
    for pid, account in query(f"SELECT post_id, account FROM targets WHERE post_id IN ({marks})", ids):
        by_post[pid].append((account,))
    return by_post

for fn in (n_plus_one, batched):
    queries = 0
    start = time.perf_counter()
    result = fn()
    print(f"{fn.__name__:<11} {queries:>3} queries   {(time.perf_counter() - start) * 1000:5.1f} ms")
assert n_plus_one() == batched()
# n_plus_one   51 queries    39.1 ms
# batched       2 queries     1.7 ms

(51 sleeps of 0.5 ms took 39 ms rather than 26 because time.sleep overshoots short sleeps on macOS. Real networks are less tidy still.) The batched version is two queries whatever N is: O(1) round trips, with O(N) work moved into the database, which is very good at it. A JOIN does the same in one query.

Object-relational mappers make N+1 easy to write by accident, because post.targets looks like reading an attribute while it quietly runs a query. SQLAlchemy’s fix is to say up front what you’ll need, with selectinload (one extra IN query per relationship, split into chunks only for very large result sets) or joinedload (a JOIN). Django has prefetch_related and select_related. Rails has includes. Every ORM has the same bug and the same cure.

The best defence I know is a test that counts queries at two sizes and asserts they’re equal. That’s a Big-O assertion: “the number of queries is O(1) in the number of rows.” The production section shows one.

Round trips dominate distributed systems

The N+1 lesson generalizes. In a system of services, count the network hops on the critical path first and the CPU work second:

• Batch. One request for N items instead of N requests: IN (...), Redis MGET and pipelines, bulk insert statements, batch endpoints.
• Move the computation to the data. A Redis Lua script that reads, checks and increments in one call is one round trip instead of three, and atomic as a bonus. The rate limiter article does exactly this.
• Run independent calls in parallel. Three sequential 50 ms calls take 150 ms; three concurrent ones take about 50. That’s not a Big-O change in total work, but latency is about the longest chain of dependent steps, and that chain is what you shortened.
• Watch fan-out depth. A request that calls 10 services, each of which calls 10 more, is 100 calls. Tail latency compounds: if each call is slow 1% of the time, a request that waits on 100 of them is slow far more often.

Space for time: caches and precomputation

Many of the biggest speedups don’t change the algorithm at all; they spend memory to avoid repeating work. Memoized Fibonacci was one. Precomputing prefix sums is another:

from itertools import accumulate

daily = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]          # messages per day

def range_sum_slow(lo, hi):                       # O(hi - lo) per question
    return sum(daily[lo:hi])

prefix = [0, *accumulate(daily)]                  # O(n) once, O(n) extra memory
def range_sum_fast(lo, hi):                       # O(1) per question
    return prefix[hi] - prefix[lo]

print(prefix)
print(range_sum_slow(2, 7), range_sum_fast(2, 7))
# [0, 3, 4, 8, 9, 14, 23, 25, 31, 36, 39]
# 21 21

An O(n) build buys O(1) answers forever after. That’s the right trade when you’ll answer many questions about data that doesn’t change much. The same idea at system scale is a cache, a materialized view or a search index, and the same question decides each one: how often is it read compared to how often it changes? Every precomputed answer has to be kept in sync with the data it was computed from, and that write cost is where the trade can turn against you.

A database index is the canonical case. It turns O(n) reads into O(log n) reads and adds O(log n) work to every insert and update of the indexed column, plus the disk space. The production section has a real decision about where that write cost wasn’t worth paying.

A short, honest note on P versus NP

Some problems have no known efficient algorithm at all. The travelling salesman problem asks for the shortest round trip through n cities. Trying every route is simple:

from math import factorial

def human(seconds):
    for unit, size in (("years", 3600 * 24 * 365), ("days", 86400), ("s", 1), ("ms", 1e-3), ("µs", 1e-6)):
        if seconds >= size:
            return f"{seconds / size:,.1f} {unit}"
    return f"{seconds * 1e9:.0f} ns"

for cities in (5, 10, 15, 20, 25):
    routes = factorial(cities - 1) // 2          # distinct round trips through every city
    print(f"{cities:>2} cities: {routes:>27,} routes   {human(routes * 1e-9):>18} at 1 ns per route")
#  5 cities:                          12 routes                12 ns at 1 ns per route
# 10 cities:                     181,440 routes             181.4 µs at 1 ns per route
# 15 cities:              43,589,145,600 routes               43.6 s at 1 ns per route
# 20 cities:      60,822,550,204,416,000 routes            1.9 years at 1 ns per route
# 25 cities: 310,224,200,866,619,719,680,000 routes    9,837,144.9 years at 1 ns per route

Factorial growth is worse than exponential. Cleverer exact algorithms exist (dynamic programming brings it to about O(n² · 2ⁿ)), but nobody knows one that runs in polynomial time, O(n^k) for some fixed k.

That’s the heart of P versus NP. P is the class of yes-or-no problems that can be solved in polynomial time. NP is the class whose answers can be checked in polynomial time: given a proposed route, checking that it visits every city and is shorter than some length is easy. Every problem in P is in NP. Whether the reverse holds, whether every quickly checkable problem is also quickly solvable, is the open question. It’s one of the Clay Mathematics Institute’s Millennium Prize Problems, and most researchers believe P ≠ NP, but nobody has proved it either way.

What it means in practice: when a problem turns out to be NP-hard (scheduling with constraints, packing, many routing problems), don’t look for a clever exact algorithm. Use a heuristic that’s good enough, an approximation algorithm with a proven bound, a solver library built for it, or exploit the fact that your real n is small. The worst move is to ship the brute force because it worked on the five-item test case.

Reviewing a design for complexity

When I read a design or a pull request with performance in mind, these are the questions, roughly in order of how often they find something:

1. What’s n, and how big does it get? Rows per tenant, items per order, members per group. The biggest tenant, not the average one.
2. How many round trips does one request make, and does that number grow with n? Any loop that contains a query, an HTTP call or a cache call is suspect.
3. What does the database do for each query? A plan you’ve looked at, against realistically sized and skewed data. At a few hundred rows every plan looks fine.
4. Is there a hidden loop? in on a list, .index, .remove, pop(0), string building, a sort inside a loop.
5. Is anything unbounded? A list that only grows, a cache with no eviction, a count of “all rows”, a request size with no cap.
6. What does the worst case cost, and who controls the input? If a user can choose n, they can choose a large one.

In production: complexity bugs in a multi-tenant backend

ezychat.io is a multi-tenant platform where AI answers customers on WhatsApp, Instagram, Messenger and web chat. The backend is Python (FastAPI and Celery) on PostgreSQL and Redis, and I’m its primary engineer. Every example below is from its code, migrations or engineering handbook, quoted as written and trimmed.

Most of the numbers come from one load-test fixture, measured on 2026-08-13: 50 organizations, 400,000 conversations and 2 million messages, with the largest tenant holding 55% of the data. The skew is deliberate. A uniform seed hides the problems below, because every tenant is small. Real multi-tenant data has one tenant that’s much bigger than the rest, and that tenant’s query plans decide the cost of the shared API.

The inbox that sorted 220,000 rows to show 50

The inbox list was the single most expensive statement on the platform. Migration 0085 records why:

**The inbox list was the most expensive statement on the platform**: 142 ms
mean, 52.9 s of database time in a 25 s run, more than the next nine
statements combined. `GET /conversations` filters on `org_id` alone and orders
by `last_message_at DESC, id DESC`. The closest existing index,
`ix_conversations_org_status_last_msg`, leads `(org_id, status,
last_message_at DESC, ...)`, and because the query never constrains `status`
Postgres cannot walk it in the requested order. It read all 220,000 of the
tenant's conversations and sorted them on disk (`Sort Method: external merge
Disk: 3872kB`) to return 50 rows.

That’s plan 2 from the SQLite example, at production shape. The plan fragment in the handbook:

Sort Method: external merge  Disk: 3872kB
->  Parallel Seq Scan on conversations  (rows=73333, loops=3)

In complexity terms, every inbox load cost O(m log m) for m conversations in the tenant, and the sort spilled to disk. The page only ever shows 50. The fix is one index whose order matches the query’s ORDER BY, after the equality column:

# Measured read paths — named for the query they serve, not for a constraint.
_READ_PATH: list[tuple[str, str, str]] = [
    ("ix_conversations_org_last_msg", "conversations", "org_id, last_message_at DESC, id DESC"),
]

With it, the query walks the index from the top and stops after 50 entries: O(log m + 50), flat no matter how big the tenant gets. 310 ms became 12.9 ms, and the disk sort disappeared. Together with the contacts fix below, end-to-end throughput across the scenario mix went from 35.4 to 70.4 requests per second, and p50 latency from 349 ms to 121 ms.

The handbook turned it into a rule, because the same mistake had already been found once before, on the leads board:

The check: for a query that filters A and orders by B, an index (A, X, B) only helps if X is also constrained by that query. If it is not, you need (A, B). Keep both indexes when both query shapes exist — the status-filtered inbox still wants the narrower one.

The contacts list had the other classic shape. Each page of 50 contacts hangs two correlated subqueries off every row, and both joined on columns with no index, so each subquery was a sequential scan, run once per contact on the page: Seq Scan on conversations at 60 ms, executed 50 times. That’s O(page × table) in a query that looks like it reads 50 rows. Indexing the two join columns took it from 3,782 ms to 18.5 ms for a page.

A delete whose cost grew with somebody else’s data

PostgreSQL creates an index for a primary key and for a unique constraint. It creates nothing for the referencing side of a foreign key. So when you delete a parent row, the database has to check every child table for rows that still point at it, and without an index on the child’s foreign-key column, each check is a sequential scan of that child table.

The test that now guards this records how it surfaced:

"""Every foreign key must have an index leading with its column.

...

That is not a theoretical cost. Before migration 0085 this schema had 86 such
foreign keys, and deleting 120,000 contacts — the PDPA erasure right the
compliance table in `00-product/non-functional-requirements.md` commits to —
ran for three and a half minutes before being cancelled, because
`conversations.contact_id` had no index and every contact removed cost one
scan of the conversation history.
"""

Do the complexity. Deleting c contacts with h conversations in the table cost O(c · h): every contact paid for a full scan of everyone’s history. With conversations emptied first, the same delete took 4.5 seconds, which shows exactly which term was the problem. With an index on conversations.contact_id, each check is a B-tree lookup and the delete becomes O(c · log h). And because deleting a contact is how ezychat honours a data-erasure request under Malaysia’s PDPA, the cost of a privacy right had been scaling with the size of the organization’s message history instead of with the data being erased.

Migration 0085 added indexes for 57 foreign keys in one pass, generated from the database catalogue rather than from memory. The test inverts the default: a new foreign key without an index fails the suite.

The interesting part is what was deliberately not indexed. Indexes are a space-time trade, and the write side of it is real:

EXEMPT: dict[tuple[str, str], str] = {
    ("conversations", "assigned_to"): (
        "conversations takes an UPDATE on every inbound message, so each extra "
        "index is a write cost on the hottest path in the product. The read "
        "filter is served by ix_conversations_assigned_status (org_id, "
        "assigned_to, status), and memberships are removed rarely enough that "
        "one sequential scan at deletion time is the better trade."
    ),
    ...
}

That’s the Expert section’s trade made explicitly. An O(n) scan that happens when a team member is removed, which is rare, is cheaper overall than an O(log n) index update on every inbound message, which is constant. Big-O tells you the cost of each operation; how often each operation happens tells you which cost to pay.

N+1, held by a test

The handbook’s standards list “no N+1 queries” as a rule, and the code is full of docstrings that name it at the exact place it would creep in. From the catalogue module:

async def load_units(
    session: AsyncSession, org_id: uuid.UUID, product_ids: list[uuid.UUID]
) -> dict:
    """Units for many products in one query — never one query per product.
    The importer, the review queue, and `search_catalog` all read units for
    a page of products at a time."""

and, in the function that diffs an import against the live catalogue: “a lazy load here would be the N+1 that only shows up on a customer’s 300-product sync.” That sentence is the whole problem in one line. N+1 doesn’t show up in development; it shows up on the biggest customer’s data.

The publishing module loads relationships through selectinload, so a page of posts costs a fixed number of queries however many posts and targets it holds:

def _load_options():
    return (
        selectinload(Post.targets).selectinload(PostTarget.social_account),
        # The delivery receipt, eager-loaded with everything else. One extra
        # query per page rather than one per target — this is the busiest
        # read in the module and an N+1 here grows with exactly the thing a
        # customer is proud of, how much they publish.
        selectinload(Post.targets).selectinload(PostTarget.attempts),
        selectinload(Post.media),
    )

Rules in comments drift. What holds the line is a test that counts SQL statements at two sizes and requires them to be equal. This one is for the conversation list:

async def test_conversation_list_is_a_single_batched_query(client):
    ...
    for _ in range(3):
        conv_id, _ = await _make_conversation(org_id, channel_id)
        await _add_message(org_id, conv_id)

    with _QueryCounter() as small:
        resp_small = await client.get("/conversations?limit=100", headers=_auth(owner))
    assert resp_small.status_code == 200

    for _ in range(15):
        conv_id, _ = await _make_conversation(org_id, channel_id)
        await _add_message(org_id, conv_id)

    with _QueryCounter() as large:
        resp_large = await client.get("/conversations?limit=100", headers=_auth(owner))
    assert resp_large.status_code == 200

    assert small.count == large.count
    assert len(resp_large.json()["items"]) == 18

_QueryCounter hooks SQLAlchemy’s before_cursor_execute event and increments a number. small.count == large.count is “queries are O(1) in the number of conversations”, written as an assertion. The publishing module has the same test for its post list (1 post against 5, each with two targets and a media item). I’d add this kind of test to any list endpoint before optimizing anything else: it’s cheap, it’s exact, and it fails the day someone adds a lazy relationship to a response model.

The same thinking applies to round trips that aren’t N+1. A function on the path the app shell blocks on fetches two facts with two scalar subqueries in one statement, and its docstring says why:

def _facts(org_id: uuid.UUID) -> Select:
    """Guardian and directory in one round trip.

    Two scalar subqueries rather than two statements, for the reason
    `catalog/setup.py` gives: this runs on the `/modules` cache-miss path that
    the app shell blocks on, and a second sequential await there is a second
    network round trip per org per minute.
    """

Two statements would be O(1) either way. The point is the constant: on a hot path, a round trip is the unit worth counting.

Counting to a hundred instead of to the end

The sidebar shows how many unread conversations an inbox has. Counting them means running the inbox’s unread rule for every thread, and for a tenant with hundreds of thousands of conversations that’s a lot of work for a number in a pill. The handbook records the measurement: counting a 220k-conversation inbox through the per-thread unread check took 1.2 s, and stopping at the hundredth unread row takes about 6 ms. So the count stops:

UNREAD_COUNT_CAP = 100


async def count_unread_inbox_items(
    ...
    cap: int = UNREAD_COUNT_CAP,
) -> int:
    """...
    Counted up to `cap` only. The sidebar shows "99+" past 99, and stopping
    at the hundredth unread row is what keeps this cheap for an org with a
    six-figure inbox, where counting every row through the per-thread
    LATERAL took over a second."""
    ...
    unread = select(literal(1)).select_from(rows).where(rows.c.unread.is_(True)).limit(cap)
    stmt = select(func.count()).select_from(unread.subquery())

LIMIT inside the count turns O(m) in the inbox size into O(min(m, 100)), which for a big inbox is a constant. The product decision and the complexity decision are the same decision: nobody acts differently on 4,312 unread than on “99+”, so there’s no reason to pay for the exact number. The result is also cached for 15 seconds per organization and cleared when a thread is read, which is the space-for-time trade on top.

Bounding a quadratic

The opening of this article timed a function that compares a generated draft with what a person actually published, to measure how much of an AI draft survived. It uses Levenshtein edit distance, which fills an n × m table: O(n · m) time. The code keeps only two rows of that table, so its memory is O(m), which is the grid exercise’s lesson applied. The time can’t be reduced that way, so it’s bounded instead:

# The longest prefix the survival measurement compares. See
# `edit_distance_ratio` — Levenshtein is quadratic, so two full-length post
# bodies (`posts.body` allows five thousand characters) would be twenty-five
# million pure-Python operations on the request that publishes a post. At
# this bound the worst case is under fifty milliseconds, and no realistic
# caption reaches it: Instagram caps at 2200 and the median is a fraction of
# that. Six hundred characters is far more than enough to answer the only
# question the number is for — did a person rewrite this?
COMPARE_MAX_CHARS = 600

I measured the same two-row loop on my laptop with random text at four lengths:

import random, string, time

def levenshtein(left, right):
    """The two-row loop from ezychat's brand/voice.py, without the bounds."""
    previous = list(range(len(right) + 1))
    for i, left_char in enumerate(left, start=1):
        current = [i]
        for j, right_char in enumerate(right, start=1):
            current.append(min(previous[j] + 1, current[j - 1] + 1,
                               previous[j - 1] + (left_char != right_char)))
        previous = current
    return previous[-1]

random.seed(0)
text = lambda n: "".join(random.choice(string.ascii_lowercase + " ") for _ in range(n))
for n in (600, 1_200, 2_400, 5_000):
    a, b = text(n), text(n)
    start = time.perf_counter()
    levenshtein(a, b)
    print(f"{n:>5,} characters each: {n * n:>10,} cells   {(time.perf_counter() - start) * 1000:7,.0f} ms")
#   600 characters each:    360,000 cells        39 ms
# 1,200 characters each:  1,440,000 cells       173 ms
# 2,400 characters each:  5,760,000 cells       706 ms
# 5,000 characters each: 25,000,000 cells     3,243 ms

Doubling the length quadruples the time, as n² says it should, and the comment’s “under fifty milliseconds” holds at 600. Without the bound, one long post would hold up its own publish request for over three seconds. The function also answers wholesale rewrites before doing any quadratic work: if one string is less than a quarter of the other’s length, the ratio can’t be higher than that, so it returns early. A cheap O(1) check in front of an expensive O(n²) one is a pattern worth stealing.

This is the general move for quadratic code you can’t replace: bound the input to what the question actually needs. A cap is a product decision as much as a technical one, which is why the comment explains the question being answered, not only the cost.

What production adds to the textbook

• n is the biggest tenant, not the average one. Every bug here was invisible on uniform, development-sized data and obvious on one skewed tenant.
• The database is where Big-O bites. A missing index or a mismatched sort order turns O(log n) into O(n log n) without changing a line of application code. Read the plan.
• Count round trips, and test the count. “Queries are constant in the page size” is the most valuable complexity assertion a backend can have, and it’s ten lines.
• Indexes and caches are trades. Each one makes a read cheaper by making some write more expensive. Write down which side you chose and why, as the foreign-key exemptions do.
• When the shape can’t change, cap n. Counting to 100 and comparing 600 characters are both “this work is O(n), so make n small on purpose.”

Cheat sheet