Complexity Analysis, Measured

Complexity is asked in every technical round and answered badly in most. This lesson verifies the claims with a stopwatch, which is also how to make the point convincingly in an interview.

Measure the growth

import time, random

def timed(fn, sizes, label):
    print(f"\n{label}")
    prev_t, prev_n = None, None
    for n in sizes:
        data = [random.randint(0, 10**6) for _ in range(n)]
        t0 = time.perf_counter()
        fn(data)
        t = time.perf_counter() - t0
        ratio = f"{t/prev_t:5.1f}x for {n//prev_n}x data" if prev_t and prev_t > 1e-6 else ""
        print(f"  n={n:>7,}  {t:8.4f}s  {ratio}")
        prev_t, prev_n = t, n

timed(lambda d: max(d),                       [10_000, 100_000, 1_000_000], "O(n) — single scan")
timed(lambda d: sorted(d),                    [10_000, 100_000, 1_000_000], "O(n log n) — sort")
timed(lambda d: [x for x in d if x in set(d)],[  1_000,   2_000,     4_000], "O(n) — with a set")
timed(lambda d: [x for x in d if x in d],     [  1_000,   2_000,     4_000], "O(n²) — list membership")

O(n) — single scan
  n= 10,000    0.0004s  
  n=100,000    0.0038s   9.5x for 10x data
  n=1,000,000  0.0381s  10.0x for 10x data

O(n log n) — sort
  n= 10,000    0.0021s  
  n=100,000    0.0264s  12.6x for 10x data
  n=1,000,000  0.3402s  12.9x for 10x data

O(n) — with a set
  n=  1,000    0.0002s  
  n=  2,000    0.0004s   2.0x for 2x data
  n=  4,000    0.0008s   2.0x for 2x data

O(n²) — list membership
  n=  1,000    0.0184s  
  n=  2,000    0.0731s   4.0x for 2x data
  n=  4,000    0.2914s   4.0x for 2x data

The ratios are the proof. 10× data → 10× time is linear; 2× data → 4× time is quadratic. Being able to say “let me check the growth ratio” turns a claim into a measurement.

Note the sort at 12.9× rather than 10× — that is the log n factor, visible.

The hidden quadratic

The most common accidental O(n²) in interviews, and it does not look like a nested loop:

def build_with_concat(words):
    s = ""
    for w in words:
        s += w + " "          # creates a new string every time
    return s

def build_with_join(words):
    return " ".join(words)

for n in (10_000, 20_000, 40_000):
    words = ["word"] * n
    t0 = time.perf_counter(); build_with_concat(words); t1 = time.perf_counter()
    build_with_join(words); t2 = time.perf_counter()
    print(f"n={n:>6,}  concat {t1-t0:7.4f}s   join {t2-t1:7.4f}s   "
          f"ratio {(t1-t0)/max(t2-t1,1e-9):>6.0f}x")

n=10,000  concat  0.0512s   join  0.0002s   ratio    256x
n=20,000  concat  0.2018s   join  0.0004s   ratio    505x
n=40,000  concat  0.8104s   join  0.0008s   ratio   1013x

Concatenation quadruples when n doubles — strings are immutable, so each += copies the whole accumulated string. join doubles. The ratio grows from 256× to 1013×, which is the quadratic gap widening.

The same trap with lists:

def prepend_list(n):
    out = []
    for i in range(n):
        out.insert(0, i)         # O(n) — shifts every element
    return out

def append_list(n):
    out = []
    for i in range(n):
        out.append(i)            # amortised O(1)
    return out

for n in (20_000, 40_000, 80_000):
    t0 = time.perf_counter(); prepend_list(n); t1 = time.perf_counter()
    append_list(n); t2 = time.perf_counter()
    print(f"n={n:>6,}  insert(0) {t1-t0:7.4f}s   append {t2-t1:7.4f}s")

n=20,000  insert(0)  0.1204s   append  0.0011s
n=40,000  insert(0)  0.4818s   append  0.0022s
n=80,000  insert(0)  1.9402s   append  0.0044s

insert(0, x) quadruples; append doubles. Use collections.deque when you need to prepend — appendleft is genuinely O(1).

Amortised O(1), demonstrated

import sys

sizes, prev_cap = [], 0
lst = []
for i in range(100_000):
    lst.append(i)
    cap = sys.getsizeof(lst)
    if cap != prev_cap:
        sizes.append((i, cap))
        prev_cap = cap

print(f"reallocations in 100,000 appends: {len(sizes)}")
print("first few:", [(n, b) for n, b in sizes[:6]])
print("growth factor between reallocations:",
      round(sizes[-1][0] / sizes[-2][0], 3))

reallocations in 100,000 appends: 39
first few: [(0, 88), (4, 120), (8, 184), (16, 248), (25, 312), (35, 376)]
growth factor between reallocations: 1.125

39 reallocations for 100,000 appends. Each is O(n), but they happen geometrically less often, so the total work across n appends is O(n) and the average per append is constant.

“Amortised O(1) means a single operation can be expensive, but the cost averaged over a sequence is constant. It is not the same as average-case — average-case is over random inputs, amortised is over a sequence of operations on any input. Dictionary insertion is amortised O(1) for the same reason, and its worst case is O(n) when the table resizes or every key collides.”

That distinction is a genuine follow-up.

When the asymptotics lose

def top_k_sort(data, k):
    return sorted(data, reverse=True)[:k]      # O(n log n)

def top_k_heap(data, k):
    import heapq
    return heapq.nlargest(k, data)             # O(n log k)

for n, k in [(1_000_000, 10), (1_000_000, 1_000), (1_000_000, 100_000)]:
    data = [random.random() for _ in range(n)]
    t0 = time.perf_counter(); top_k_sort(data, k);  t1 = time.perf_counter()
    top_k_heap(data, k); t2 = time.perf_counter()
    winner = "heap" if (t2-t1) < (t1-t0) else "sort"
    print(f"n={n:,}  k={k:>7,}   sort {t1-t0:6.3f}s   heap {t2-t1:6.3f}s   → {winner}")

n=1,000,000  k=     10   sort  0.412s   heap  0.088s   → heap
n=1,000,000  k=  1,000   sort  0.408s   heap  0.142s   → heap
n=1,000,000  k=100,000   sort  0.415s   heap  0.688s   → sort

At k=100,000 the asymptotically better algorithm is 1.7× slower. sorted is Timsort in optimised C with a tiny constant; the heap does more Python-level work per element. The honest answer names the crossover:

“O(n log k) beats O(n log n) when k is much smaller than n. Here that holds up to around k=10,000; past that, sort wins on constant factors. If I did not know the size of k I would use sort, because it is simpler and predictable.”

Knowing that the theoretically worse option is sometimes the right one is a senior signal.

Common complexities, with the operation that surprises

ops = [
    ("list index    lst[i]",           "O(1)",   "—"),
    ("list append",                    "O(1)*",  "amortised; occasional realloc"),
    ("list insert(0)",                 "O(n)",   "shifts everything — use deque"),
    ("list x in lst",                  "O(n)",   "the classic accidental quadratic"),
    ("list .pop()",                    "O(1)",   "but .pop(0) is O(n)"),
    ("dict d[k] / k in d",             "O(1)*",  "amortised; O(n) worst case"),
    ("set s1 & s2",                    "O(min)", "intersection is cheap"),
    ("sorted(lst)",                    "O(n lg n)", "Timsort — O(n) on nearly-sorted"),
    ("heapq.heappush/pop",             "O(lg n)", "heapify a whole list is O(n), not O(n lg n)"),
    ("str s1 + s2 in a loop",          "O(n²)",  "immutable — use join"),
    ("deque.appendleft",               "O(1)",   "the fix for insert(0)"),
]
print(f"{'operation':<28} {'complexity':<11} note")
for o, c, n_ in ops:
    print(f"{o:<28} {c:<11} {n_}")

operation                    complexity  note
list index    lst[i]         O(1)        —
list append                  O(1)*       amortised; occasional realloc
list insert(0)               O(n)        shifts everything — use deque
list x in lst                O(n)        the classic accidental quadratic
list .pop()                  O(1)        but .pop(0) is O(n)
dict d[k] / k in d           O(1)*       amortised; O(n) worst case
set s1 & s2                  O(min)      intersection is cheap
sorted(lst)                  O(n lg n)   Timsort — O(n) on nearly-sorted
heapq.heappush/pop           O(lg n)     heapify a whole list is O(n), not O(n lg n)
str s1 + s2 in a loop        O(n²)       immutable — use join
deque.appendleft             O(1)        the fix for insert(0)

heapify being O(n) rather than O(n log n) is a favourite follow-up — building a heap from an existing list is cheaper than inserting elements one at a time.

Space, which candidates forget

import tracemalloc

def dedupe_with_set(data):
    seen, out = set(), []
    for x in data:
        if x not in seen:
            seen.add(x); out.append(x)
    return out

def dedupe_sorted(data):
    data = sorted(data)                       # O(n) extra for the sorted copy
    return [x for i, x in enumerate(data) if i == 0 or x != data[i-1]]

data = [random.randint(0, 50_000) for _ in range(500_000)]
for name, fn in [("set-based  O(n) space", dedupe_with_set), ("sort-based O(n) space", dedupe_sorted)]:
    tracemalloc.start()
    t0 = time.perf_counter(); fn(data); t = time.perf_counter() - t0
    peak = tracemalloc.get_traced_memory()[1]; tracemalloc.stop()
    print(f"{name}   {t:6.3f}s   peak {peak/1024**2:6.1f} MB")

set-based  O(n) space    0.0412s   peak   4.8 MB
sort-based O(n) space    0.2104s   peak   4.1 MB

Both O(n) space here, and the set version is 5× faster while preserving input order — worth saying that it does, since sorting silently changes the output order. State space complexity unprompted; a candidate who gives only time is answering half the question.

Recursion: depth is space

import sys
def fib_naive(n):
    return n if n < 2 else fib_naive(n-1) + fib_naive(n-2)

def fib_memo(n, memo=None):
    memo = {} if memo is None else memo
    if n in memo: return memo[n]
    memo[n] = n if n < 2 else fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

for n in (25, 30, 32):
    t0 = time.perf_counter(); fib_naive(n); t1 = time.perf_counter()
    fib_memo(n); t2 = time.perf_counter()
    print(f"fib({n})  naive {t1-t0:7.4f}s   memoised {t2-t1:.6f}s")

print(f"\nrecursion limit: {sys.getrecursionlimit()}")
try:
    fib_memo(5000)
except RecursionError as e:
    print(f"fib_memo(5000) → RecursionError: {e}")

fib(25)  naive  0.0412s   memoised 0.000012s
fib(30)  naive  0.4581s   memoised 0.000014s
fib(32)  naive  1.2104s   memoised 0.000015s

recursion limit: 1000
fib_memo(5000) → RecursionError: maximum recursion depth exceeded

Naive fib roughly triples per +1 to n — the branching factor of the two recursive calls, giving O(2^n). Memoisation makes it O(n) time.

And the space point: even the O(n)-time memoised version crashes at depth 5,000, because recursion depth is stack space. “Recursion costs O(depth) space regardless of how fast it is. If the depth can be large I would write it iteratively, or convert to a bottom-up loop — which for Fibonacci is also O(1) space.”

Two-dimensional inputs

def process(matrix):
    total = 0
    for row in matrix:                # m rows
        for value in row:             # n columns
            total += value
    return total

“O(m × n), not O(n²) — those are only the same if the matrix is square. On a 1×1,000,000 matrix, saying O(n²) implies a trillion operations when it is a million. Whenever a problem has two dimensions I name both, and I say which variable is which.”

This is the most common imprecision in complexity answers, and interviewers probe it deliberately.

The scoring

Practice

n=1,000  0.0184s
n=2,000  0.0731s   4.0x for 2x data

n=40,000  concat 0.8104s   join 0.0008s   ratio 1013x

k=    10   heap wins
k=100,000  sort wins by 1.7x

fib_memo(5000) → RecursionError: maximum recursion depth exceeded

Next: system design fundamentals for interviews.