Complexity Analysis: Big-O from first principles

01The problem Big-O actually solves

You're on-call. A batch job that processed 10K records in 2 seconds suddenly gets 10M. Will it take ~30 minutes (linear — annoying), ~3 weeks (quadratic — page someone), or ~heat death of the universe (exponential — redesign)?

You can't answer by timing code on your laptop — wall-clock depends on hardware, load, cache temperature. So we ask a sharper question:

The one-sentence definition (know it): f(n) is O(g(n)) if, past some input size, f(n) is bounded above by a constant multiple of g(n). Translation: "eventually, my cost grows no faster than g(n), ignoring constants."

Why we legally drop constants and small terms

3n² + 50n + 1000 → O(n²). At n = 1,000,000 the n² term is 3·10¹², while 50n is 5·10⁷ — the linear term contributes 0.001% of the work. Big-O describes the large-n regime, which is exactly the regime where you care.

02The seven curves, with real intuition

O(1) — flat, not fast

The work doesn't depend on input size. A dict lookup in a 10-element dict and a 10-million-element dict cost roughly the same. "Constant" can still be a big constant — it just doesn't grow.

O(log n) — the most underappreciated curve in computing

Every step cuts the remaining problem by a constant fraction. That's the signature. Hear "halve", "binary", "tree height", "divide the range" → think log.

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:               # runs ~log2(n) times
        mid = (lo + hi) // 2
        if a[mid] == target: return mid
        if a[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1

O(n) — one pass (or two, or five)

Touch each element a constant number of times. Two passes is still O(n) — but say "I make two passes" out loud anyway; it signals you know and chose to ignore the constant.

O(n log n) — "sort-shaped"

Two ways to get here: O(log n) levels of O(n) work each (merge sort), or n operations at O(log n) each (n pushes through a heap). Rule of thumb: if your solution sorts, you're at least n log n. Comparison sorting cannot beat it — n! orderings, each comparison halves the candidates, so you need ≥ log₂(n!) ≈ n log n comparisons.

O(n²) — the all-pairs shape

for i in range(n):
    for j in range(i + 1, n):   # every pair: n(n-1)/2 → O(n²)
        ...

n = 10⁴ → 10⁸ comparisons → seconds in Python. n = 10⁵ → 10¹⁰ → minutes-to-hours. Heuristic: if n can reach 10⁵, quadratic times out — the interviewer wants n log n or n.

O(2ⁿ) and O(n!) — combinatorial explosions

"Every subset" = 2ⁿ. "Every ordering" = n!. Only acceptable when n ≤ ~20 (subsets) or n ≤ ~10 (orderings) — which is exactly the range where interviewers expect backtracking (file 07).

03Reading complexity off code — three rules

for x in items:          # O(n) iterations…
    if x in some_list:  # …× O(n) scan
        ...              # total: O(n²)

for x in items:          # O(n) iterations…
    if x in some_set:   # …× O(1) hash
        ...              # total: O(n)

Python costs you must know cold

04Space — the forgotten sibling

Same idea, applied to extra memory (by convention, the input doesn't count).

When an interviewer asks "can you do better?", your first two thoughts, in order:

1. Trade space for time? — hashmap, prefix sums, memoization
2. Exploit structure? — sorted input → binary search / two pointers

05Amortized analysis — why append is O(1) even when it isn't

Python lists are dynamic arrays: contiguous memory with spare capacity. Usually append drops into a free slot — O(1). When full, Python allocates bigger and copies all n elements — that one call is O(n).

capacity 4:  [a][b][c][d]                 append(e) → FULL!
                  │
                  ▼  allocate 8 · copy 4 · insert
capacity 8:  [a][b][c][d][e][ ][ ][ ]     ← next 3 appends: cheap O(1)

The banker's argument (say this one out loud): charge every append 3 coins. One pays for the insert; two go into the bank. When a resize must copy n elements, the bank — filled by the n/2 appends since the last resize — pays for the whole copy. No operation ever goes into debt → amortized O(1).

Equivalently: total copy work to reach size n with doubling is n/2 + n/4 + … ≈ n. So n appends cost ≈ 2n → O(1) each.

Where amortized thinking wins interviews

• list.append and hashmap inserts (resize at load factor) — amortized O(1)
• Queue-from-two-stacks: each element moves at most twice → amortized O(1) per op
• Monotonic stack loops (file 03): the inner while looks nested, but each element is pushed and popped once → total O(n)

06Best / average / worst — which to report

Default to worst case unless told otherwise. The three classic splits:

07Narrating analysis — the meta-skill being graded

Interviewers grade the narration as much as the answer. The rhythm:

1. Before coding, state the target. "Brute force is O(n²) — all pairs. n is up to 10⁵ so that's 10¹⁰ ops — too slow. I'll aim for O(n) with a hashmap." Thirty seconds; enormous signal.
2. While coding, price what matters. "This in is against a set, so O(1)… this slice copies, but it's outside the loop."
3. After coding, state both bounds unprompted. "Time O(n) — one pass, O(1) per element. Space O(n) worst case for the map."

Phrases that buy goodwill

• "Let me get a correct brute force first, then optimize." (then actually do it)
• "The bottleneck is this membership test — a set fixes it."
• "This is amortized O(1) — one call can resize, but n calls total O(n)."
• "Recursion depth is O(n) worst case; I can convert to iterative if stack limits worry us."

08The decoder ring — constraints reveal the intended answer

The constraint in the problem statement is a hint about the intended complexity. Read it first, always:

Calibration: Python does roughly ~10⁷ simple ops/second pessimistically; judges budget a few seconds.

09Feel the curves — interactive

10Rapid-fire interview Q&A

11Self-test — answer before you peek

1. Define Big-O in one sentence a junior engineer would understand.
2. Simplify: O(5n² + 3n log n + 200n + 7).
3. lst.pop() vs lst.pop(0) — costs and why?
4. Explain amortized O(1) append using the doubling argument, ≤ 3 sentences.
5. n ≤ 10⁵: what complexities are viable? What does n ≤ 20 hint instead?
6. Extra space of recursive DFS on a balanced tree? On a degenerate stick?
7. Why can't any comparison sort beat O(n log n)?
8. One worst-case scenario each: quicksort, hashmap lookup, BST insert.
9. What's wrong with while target not in seen_list: inside a loop, and the fix?
10. Say your solution's time and space in two sentences, interviewer-style.

Source: 01-dsa/01-complexity-analysis.mdNext: Arrays, Strings & Hashing →