Common complexities — O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), O(n!): Worked examples

Before anything, one word we lean on constantly:

The scenario matrix

Every complexity puzzle in this chapter is one of these cells. Each worked example below is tagged with the cell(s) it covers, so together they fill the whole grid.

Cell	Case class	What triggers it	Answer class	Example
A	Fixed work, no loop over data	direct index / arithmetic	$O (1)$	Ex 1
B	Loop divides variable by constant	`n = n // 2`, `i *= 3`	$O (lo g n)$	Ex 2
C	Single pass, one op per element	one `for` over the array	$O (n)$	Ex 3
D	Sequential loops (the "add" trap)	loop, then another loop	still $O (n)$	Ex 4
E	Nested full loops (the "multiply")	`for` inside `for`	$O (n^{2})$	Ex 5
F	Triangular nested loop	inner starts at `i`	still $O (n^{2})$	Ex 6
G	Divide-and-conquer recursion	split in half + linear merge	$O (n lo g n)$	Ex 7
H	Branching recursion (double call)	`f(n-1)+f(n-1)`	$O (2^{n})$	Ex 8
I	Degenerate / edge inputs	$n = 0$ , $n = 1$ , empty	class still holds	Ex 9
J	Real-world word problem	forecast a runtime	pick the class	Ex 10
K	Exam twist: mixed / misleading	loop bound tied to a log	careful reading	Ex 11

Worked examples

Cell A — constant, no dependence on $n$

Worked example Ex 1 — Is the middle element even?

def middle_even(arr):     # arr has length n
    m = arr[len(arr) // 2]
    return m % 2 == 0

Forecast: guess the class before reading on. Bigger array → more work, or not?

Compute the middle index len(arr)//2. Why this step? One arithmetic operation — length is stored, not counted by walking the array, so this is a single step regardless of $n$ .
Read arr[...]. Why this step? An array index is a direct address lookup — one operation, independent of how long the array is (Cell A's signature: no loop touches the data).
One modulo + one compare. Why this step? Two more fixed operations.

Total $T (n) = 3$ operations for any $n$ . Verify: $T (10) = 3$ , $T (1 0^{6}) = 3$ . Same → work does not grow with $n$ → $O (1)$ .

Cell B — logarithmic: dividing, not subtracting

Worked example Ex 2 — Counting halvings

def count_halvings(n):
    steps = 0
    while n > 1:
        n = n // 2      # halve each iteration
        steps += 1
    return steps

Forecast: for n = 64, how many times does the loop run — 64? 32? something small?

Watch the variable shrink: $64 \to 32 \to 16 \to 8 \to 4 \to 2 \to 1$ . Why this step? The signature of $O (lo g n)$ is the variable being divided by a constant factor each iteration, not decremented by one.
Set up the stopping condition. Why this step? After $k$ halvings we have $n / 2^{k}$ ; the loop stops when that reaches $1$ : $\frac{n}{2 ^{k}} = 1 \Rightarrow 2^{k} = n \Rightarrow k = lo g_{2} n .$
Read off $k$ . Why? $k$ is exactly the loop count. For $n = 64$ : $lo g_{2} 64 = 6$ .

Verify: count the arrows above — $64 \to 32 \to 16 \to 8 \to 4 \to 2 \to 1$ is $6$ steps. Matches $lo g_{2} 64 = 6$ → $O (lo g n)$ . See Binary-Search for the same halving in action.

Figure — Common complexities — O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), O(n!)

Cell C — linear: one touch per element

Worked example Ex 3 — Find the maximum

def find_max(arr):        # length n
    best = arr[0]
    for x in arr:         # visits each element once
        if x > best: best = x
    return best

Forecast: does looking at every element once make this $O (n)$ or $O (n^{2})$ ?

One pass, constant work per element. Why this step? The loop body (a compare, maybe an assign) is bounded — it does not depend on $n$ . Doing a fixed job $n$ times gives $T (n) = c \cdot n$ .
Drop the constant $c$ . Why? Big-O keeps only growth shape: $c \cdot n$ and $n$ grow identically.

Verify: double the input ( $n \to 2 n$ ) and the loop runs twice as many times — linear scaling → $O (n)$ .

Cell D — the sequential-loop trap (add, don't multiply)

Worked example Ex 4 — Two loops in a row

for x in arr: sum1 += x        # n iterations
for y in arr: sum2 += y*y      # n more iterations

Forecast: "two loops" — is this $O (n^{2})$ ? (This is the #1 mistake.)

Count each loop separately. Why this step? The second loop runs after the first finishes; it is not inside it. Nothing multiplies.
Add the counts. Why? Sequential work is additive: $T (n) = n + n = 2 n$ .
Drop the constant. $2 n \to O (n)$ .

Verify: at $n = 1000$ the machine does $\approx 2000$ ops, not $1 0^{6}$ . If it were nested you'd get $n^{2} = 1 0^{6}$ . The gap proves sequential $\neq =$ nested → $O (n)$ .

Cell E — nested full loops: quadratic

Worked example Ex 5 — Compare all pairs

for i in range(n):
    for j in range(n):        # full n, not i..n
        if arr[i] == arr[j]: count += 1

Forecast: every element paired with every element — what shape does the work make?

Inner loop cost per outer step. Why this step? For each fixed i, the inner loop runs a full $n$ times.
Multiply, because nested. Why? Nested loops multiply their counts: $T (n) = n \times n = n^{2}$ .
State class. $O (n^{2})$ .

Verify: the work forms a full $n \times n$ grid of pairs (see figure). At $n = 4$ : $16$ inner executions. Plug $n = 4$ into $n^{2} = 16$ . ✓

Cell F — triangular loop is still quadratic

Worked example Ex 6 — Inner loop starts at

i

for i in range(n):
    for j in range(i, n):     # starts at i, shrinks
        do_constant_work()

Forecast: the inner loop does less work each time — does that drop us below $O (n^{2})$ ?

Count inner iterations per i. Why this step? For a given i, j runs from i to n-1 → that's $n - i$ iterations.
Sum over all i. Why? Total work is the sum of the per-row counts: $\sum_{i = 0}^{n - 1} (n - i) = n + (n - 1) + \dots + 1 = \frac{n ( n + 1 )}{2} .$
Expand and keep the dominant term. Why? $\frac{n ( n + 1 )}{2} = \frac{n ^{2}}{2} + \frac{n}{2}$ . The $n^{2} /2$ term dominates; drop the $\frac{1}{2}$ and the $+ n /2$ .

Verify: the executed cells form the triangle in the figure — exactly half the full grid. Half of $n^{2}$ is still $O (n^{2})$ . At $n = 4$ : $\frac{4 \cdot 5}{2} = 10$ inner runs → $O (n^{2})$ .

Cell G — divide-and-conquer: $O (n lo g n)$

Worked example Ex 7 — Merge sort's recurrence

def merge_sort(arr):          # length n
    if len(arr) <= 1: return arr
    mid = len(arr)//2
    L = merge_sort(arr[:mid]) # solve half
    R = merge_sort(arr[mid:]) # solve other half
    return merge(L, R)        # linear-time combine

Forecast: we split and recurse and merge — does that stack up to $O (n^{2})$ , or something gentler?

Write the recurrence. Why this step? Two half-sized subproblems plus a linear merge: $T (n) = 2 T (n /2) + c n .$
Count the levels. Why? Halving from $n$ down to $1$ takes $lo g_{2} n$ levels (same halving math as Ex 2). See Recurrence-Relations.
Count work per level. Why? At every level the merges together touch all $n$ items → $c n$ work per level, regardless of how many pieces.
Multiply levels × per-level work. $c n \times lo g_{2} n = O (n lo g n)$ . (Master-Theorem confirms case 2.)

Verify: the recursion tree (figure) has $lo g_{2} 8 = 3$ levels for $n = 8$ , each summing to $c n$ . Total $= 3 c n$ , matching $n lo g_{2} n = 8 \cdot 3 = 24$ (with $c = 1$ ). ✓ See Merge-Sort.

Cell H — branching recursion: $O (2^{n})$

Worked example Ex 8 — Naive recursive Fibonacci

def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)   # TWO recursive calls

Forecast: the number shrinks by only $1$ each call — sounds linear. Trap or truth?

Spot the double call. Why this step? Each call spawns two more calls. Branching (not shrinking) is what explodes.
Bound the recurrence. Why? Ignoring the small $- 2$ vs $- 1$ difference, $T (n) \approx 2 T (n - 1) + c$ . Unrolling: $T (n) \approx 2 (2 T (n - 2) + c) + c = 4 T (n - 2) + 3 c = \dots \approx 2^{n} .$
State class. Roughly $O (2^{n})$ (exactly it's $\approx ϕ^{n}$ , still exponential). See Dynamic-Programming for the fix down to $O (n)$ .

Verify: count the calls for fib(5). Building the tree gives $15$ calls; the bound $2^{5} = 32$ is a (loose) upper cap and $2^{5} - 1 = 31 \geq 15$ . Exponential growth confirmed → doubling n roughly squares the work.

Cell I — degenerate & edge inputs

Worked example Ex 9 — Does

$n = 0$ or $n = 1$ break the class? Take find_max (Ex 3) and count_halvings (Ex 2) at their edges.

Forecast: do tiny inputs change the class, or just the constant?

Empty array, $n = 0$ . Why this step? find_max does $0$ passes — $T (0) =$ const setup. Big-O describes $n \to \infty$ , so a single finite point can't change the class.
Single element, $n = 1$ . Why? count_halvings(1): the while n>1 guard is false immediately → $0$ iterations. And $lo g_{2} 1 = 0$ — the formula agrees.
Single element, $n = 1$ , in merge sort. Why? len(arr)<=1 returns instantly — the recursion base case. $T (1) = O (1)$ , which is exactly what the recurrence needs to bottom out.

Verify: $lo g_{2} 1 = 0$ predicts zero halvings — matches the loop running $0$ times. Edge inputs obey the same formulas; classes are asymptotic, so $edges never demote the class$ .

Cell J — real-world forecast

Cell K — exam twist: loop bound tied to a log

Worked example Ex 11 — The sneaky combined loop

i = 1
while i < n:               # multiplies i each step
    for j in range(n):     # full inner pass
        do_constant_work()
    i = i * 2

Forecast: outer loop looks like $O (n)$ , inner is $O (n)$ — is the answer $O (n^{2})$ ? (The twist: it isn't.)

Analyse the outer loop alone. Why this step? i doubles each time (i*2), so it reaches $n$ after $lo g_{2} n$ steps — that's Cell B's signature, not a linear counter.
Analyse the inner loop. Why? A plain range(n) → $n$ iterations every time, independent of i.
Multiply (nested). Why? Inner is nested inside outer: $T (n) = outer lo g_{2} n \times inner n = O (n lo g n)$ .

Verify: at $n = 16$ : outer runs at $i = 1, 2, 4, 8$ → $4 = lo g_{2} 16$ times; inner runs $16$ each → $4 \times 16 = 64$ ops. Compare $n lo g_{2} n = 16 \times 4 = 64$ . ✓ Not $n^{2} = 256$ — the doubling outer loop saved you. See 3.1.03-Best-Worst-Average-Case for how bounds like this shift by input shape.

Recall Quick self-test

Loop that does i *= 3 until i >= n — which class? ::: $O (lo g n)$ — divide-by-constant signature (base 3, but base is irrelevant). Triangular nested loop for j in range(i, n) — class? ::: $O (n^{2})$ — it's half the full grid; half of $n^{2}$ is still $n^{2}$ . fib(n) with two recursive calls — class? ::: $O (2^{n})$ — branching recursion doubles work. $O (n^{2})$ scan of $n = 1 0^{5}$ at $1 0^{9}$ ops/s — runtime? ::: $\approx 10$ seconds ( $1 0^{10} /1 0^{9}$ ). Outer loop that doubles i, inner full range(n) — class? ::: $O (n lo g n)$ — $lo g n$ outer × $n$ inner.