Time & Space Complexity

A first-principles teaching session — theory, worked examples, and a reference sheet you'll actually use.

1. Theory — why we count, and how

The motivation

Two algorithms solve the same problem. One takes 2 seconds on your laptop; the other takes 8 seconds. Is the first "better"? Not necessarily. Run them on a different machine, or a bigger input, and the answer can flip.

We need a measurement that is machine-independent and scales with input size. That's what complexity analysis gives us: not "how many milliseconds," but "how does the work grow as n grows?"

Core idea. We count elementary operations as a function of input size n, then describe how that function grows. Constants and low-order terms don't matter for large n — only the shape of the growth does.

Asymptotic notations — the formal definitions

These aren't hand-wavy. Each one is a precise statement about how one function behaves relative to another for large enough n.

Big-O — upper bound

f(n) = O(g(n)) means: there exist positive constants c and n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀.

Read it as: past some point, f grows no faster than a constant multiple of g.

Big-Ω (Omega) — lower bound

f(n) = Ω(g(n)) means: there exist positive c, n₀ such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n₀.

Read as: past some point, f grows at least as fast as a constant multiple of g.

Big-Θ (Theta) — tight bound

f(n) = Θ(g(n)) iff f(n) = O(g(n)) and f(n) = Ω(g(n)). Same growth rate, up to constants.

little-o and little-ω — strict bounds

f(n) = o(g(n)) means f grows strictly slower: for every c > 0, eventually f(n) < c·g(n). Equivalently, lim f/g = 0.

f(n) = ω(g(n)) is the strict lower version: lim f/g = ∞.

Common trap. "Big-O" is an upper bound, not "the exact growth." Saying insertion sort is O(n²) is technically also correct if you say O(n³) — but useless. In interviews, always give the tightest bound you can (Θ), even if you write it as O.

The growth rate hierarchy

Memorize this ordering — it's the ladder you'll climb every time you analyze code:

O(1) < O(log log n) < O(log n) < O(√n) < O(n)
     < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

The rules of simplification

When you count operations, you'll get messy expressions like 3n² + 7n + 42. Then you apply the rules:

Drop constant factors

O(3n) = O(n). The machine's clock speed is a constant multiplier; we don't care.

Drop lower-order terms

O(n² + n + 100) = O(n²). For large n, n² dominates.

Sum rule (sequential blocks)

If block A is O(f) and block B is O(g), running them one after another is O(f + g) = O(max(f, g)).

Product rule (nested blocks)

If block A runs f(n) times and each run does g(n) work, the total is O(f · g). This is the nested-loop rule.

Best, average, and worst case

Same algorithm can behave very differently depending on input:

Worst case — maximum work over any input of size n. What we usually mean by "the complexity."
Best case — minimum work. Rarely interesting alone.
Average case — expected work, assuming some distribution over inputs. Needs a probabilistic argument.

Example: quicksort is Θ(n log n) on average, but Θ(n²) in the worst case (already-sorted input with bad pivot).

Amortized analysis — the honest average

Sometimes a single operation is expensive, but it can only be expensive rarely. Amortized analysis pays attention to that.

Classic example: dynamic array push (Python list, C++ vector). Most pushes are O(1). But when the array is full, we allocate a new one twice as big and copy everything — O(n). Over any sequence of n pushes, total work is O(n), so amortized cost per push is O(1).

Three methods to prove amortized bounds: aggregate (total work / number of ops), accounting (charge extra to cheap ops as credit), potential (define a potential function that "pays" for expensive ops).

Space complexity — two flavors

Total space — input + auxiliary. Everything the algorithm touches.
Auxiliary space — extra memory used beyond the input. Usually what interviewers mean by "space complexity."

Recursion counts. A recursive function with depth d uses at least O(d) auxiliary space for the call stack, even if it stores nothing else.

Common space patterns

Two-pointer / in-place — O(1)
Linear scan with hash set — O(n)
Recursion on a balanced tree — O(log n) stack
Recursion on a linked list / skewed tree — O(n) stack
Dynamic programming table — O(state space)

Recursion complexity — three methods

When your algorithm calls itself, you get a recurrence relation like T(n) = 2T(n/2) + n. Three tools to solve it:

Substitution method — guess the answer, prove by induction.
Recursion tree — draw the tree of calls, sum work at each level, sum levels.
Master Theorem — a formula for the common case T(n) = aT(n/b) + f(n). See tab 4.

2. Growth Explorer — see the ladder

Toggle complexity classes on and off. Move the slider to change n. You'll see why an O(n²) algorithm that beats an O(n log n) one at n = 10 loses badly at n = 1000.

Max n: 50

Y-axis: linear log

Concrete impact

Assume 10⁸ operations per second. Here's how long an algorithm takes at various input sizes:

Complexity	n=10	n=100	n=1,000	n=10⁶
O(log n)	~0	~0	~0	0.2 μs
O(n)	0.1 μs	1 μs	10 μs	10 ms
O(n log n)	0.3 μs	7 μs	100 μs	200 ms
O(n²)	1 μs	100 μs	10 ms	~3 hours
O(n³)	10 μs	10 ms	10 s	32k years
O(2ⁿ)	10 μs	10¹³ years	—	—
O(n!)	36 ms	—	—	—

The lesson. Constant factors matter for small n. Growth rate matters for anything real. The gap between O(n log n) and O(n²) is the difference between "solves in a second" and "solves overnight."

3. Worked Examples — graded

Try to derive the complexity yourself before opening the answer. The point isn't to memorize; it's to build the muscle of counting.

Level 1 — foundations

E1. Sum an arrayeasy

def total(arr):
    s = 0
    for x in arr:
        s += x
    return s

Analyze: The loop runs n times, each iteration does O(1) work.

Time: Θ(n) • Space: Θ(1) auxiliary

E2. Two independent loopseasy

for i in range(n):
    do_work()

for j in range(n):
    do_work()

Analyze: Sum rule — n + n = 2n. Drop the constant.

Time: Θ(n)

Note: Even if the second loop had size m instead of n, we'd write O(n + m), not O(max), unless we know their relationship.

E3. Nested loopseasy

for i in range(n):
    for j in range(n):
        do_work()

Analyze: Product rule — n × n iterations.

Time: Θ(n²)

Level 2 — patterns that fool people

E4. Doubling loopmedium

i = 1
while i < n:
    do_work()
    i *= 2

Analyze: After k iterations, i = 2ᵏ. Loop stops when 2ᵏ ≥ n, i.e. k = ⌈log₂ n⌉.

Time: Θ(log n)

Any time you see multiplicative progress toward a bound, think logarithm.

E5. Triangular nested loopmedium

for i in range(n):
    for j in range(i):
        do_work()

Analyze: Total iterations = 0 + 1 + 2 + ... + (n-1) = n(n-1)/2.

Time: Θ(n²) — same as full nested despite doing "half the work."

Constant factors — even the "half" — vanish in Big-O.

E6. Outer linear, inner logarithmicmedium

for i in range(n):
    j = 1
    while j < n:
        j *= 2

Analyze: Outer loop: n. Inner loop: log n (per E4).

Time: Θ(n log n)

E7. Harmonic loop (surprises)medium

for i in range(1, n+1):
    for j in range(0, n, i):
        do_work()

Analyze: Inner loop runs ⌈n/i⌉ times. Total: n/1 + n/2 + n/3 + ... + n/n = n·H(n) where H(n) is the harmonic number, ≈ ln n.

Time: Θ(n log n)

This shows up in sieve-of-Eratosthenes analysis.

Level 3 — recursion and the tricky ones

E8. Binary searchhard

def bsearch(arr, lo, hi, target):
    if lo > hi: return -1
    mid = (lo + hi) // 2
    if arr[mid] == target: return mid
    if arr[mid] < target:
        return bsearch(arr, mid+1, hi, target)
    return bsearch(arr, lo, mid-1, target)

Recurrence: T(n) = T(n/2) + O(1)

Solve: Halving n until it hits 1 takes log₂ n steps.

Time: Θ(log n) • Space: Θ(log n) recursive stack, Θ(1) iterative

E9. Merge sorthard

def msort(a):
    if len(a) <= 1: return a
    m = len(a) // 2
    left  = msort(a[:m])
    right = msort(a[m:])
    return merge(left, right)   # O(n)

Recurrence: T(n) = 2T(n/2) + Θ(n)

Recursion tree: depth = log n, work at each level = n (splitting/merging), total = n log n.

Time: Θ(n log n) • Space: Θ(n) auxiliary for the merge buffer + Θ(log n) stack

E10. Fibonacci — naive recursionhard

def fib(n):
    if n < 2: return n
    return fib(n-1) + fib(n-2)

Recurrence: T(n) = T(n-1) + T(n-2) + O(1)

Solve: This solves to Θ(φⁿ) where φ = (1+√5)/2 ≈ 1.618. Loosely, O(2ⁿ).

Time: Θ(φⁿ) ≈ O(2ⁿ) • Space: Θ(n) call stack depth

With memoization: Θ(n) time, Θ(n) space. With iterative rolling variables: Θ(n) time, Θ(1) space.

E11. Repeated square-root shrinkhard

i = n
while i > 1:
    do_work()
    i = int(i ** 0.5)

Analyze: Let i_k be the value after k iterations. i_k = n^(1/2ᵏ). Loop stops when i_k ≤ 1, i.e. when n^(1/2ᵏ) ≤ 2, i.e. 2ᵏ ≥ log₂ n, i.e. k ≥ log₂ log₂ n.

Time: Θ(log log n)

This shows up in van Emde Boas trees. Absurdly fast — log log 10⁹ ≈ 5.

E12. Dynamic array push (amortized)hard

Setup: Array doubles when full. Push is O(1) normally but O(size) when it triggers a resize.

Aggregate analysis: After n pushes, resizes happened at sizes 1, 2, 4, 8, ..., n. Total resize work = 1 + 2 + 4 + ... + n ≈ 2n. Plus n normal pushes = 3n total work.

Cost per push, amortized = 3n / n = 3.

Amortized Time per push: Θ(1) • Worst-case single push: Θ(n)

4. Master Theorem

For divide-and-conquer recurrences of the form:

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

where a ≥ 1 and b > 1 are constants and f(n) is asymptotically positive.

Define the critical exponent c* = log_b(a). Then compare f(n) with n^(c*):

Case	Condition	Solution
1	f(n) = O(n^(c* − ε)) for some ε > 0	T(n) = Θ(n^(c*))
2	f(n) = Θ(n^(c*) · log^k n), k ≥ 0	T(n) = Θ(n^(c*) · log^(k+1) n)
3	f(n) = Ω(n^(c* + ε)) & regularity holds	T(n) = Θ(f(n))

Intuition. The recursion tree has a^(log_b n) = n^(c*) leaves. Case 1: leaves dominate (work at the bottom). Case 2: every level does equal work (log n levels of equal cost). Case 3: root dominates (work at the top).

Interactive calculator

Enter a, b, and the exponent d in f(n) = Θ(n^d). (Sticking to polynomial f for simplicity.)

a (subproblem count) b (shrink factor) d (exponent in f(n) = n^d)

Classic worked examples

Recurrence	a, b, c*	Case	Solution	Algorithm
T(n) = 2T(n/2) + n	2, 2, 1	2 (k=0)	Θ(n log n)	merge sort
T(n) = T(n/2) + O(1)	1, 2, 0	2 (k=0)	Θ(log n)	binary search
T(n) = 2T(n/2) + O(1)	2, 2, 1	1	Θ(n)	tree traversal
T(n) = 3T(n/2) + n	3, 2, log₂3≈1.58	1	Θ(n^log₂3)	Karatsuba multiplication
T(n) = 8T(n/2) + n²	8, 2, 3	1	Θ(n³)	naive matrix mult
T(n) = 7T(n/2) + n²	7, 2, log₂7≈2.81	1	Θ(n^log₂7)	Strassen's matrix mult
T(n) = 2T(n/2) + n²	2, 2, 1	3	Θ(n²)	work concentrated at top

Master Theorem doesn't cover everything. It fails when f(n) is not polynomial (e.g. n / log n), when the recurrence has non-constant a or b, or when subproblems are of different sizes (e.g. T(n) = T(n/3) + T(2n/3) + n). Fall back on recursion trees.

5. Formula Sheet

Notation cheatsheet

O(g) — upper bound • f ≤ c·g eventually
Ω(g) — lower bound • f ≥ c·g eventually
Θ(g) — tight bound • both O and Ω
o(g) — strictly smaller • lim f/g = 0
ω(g) — strictly larger • lim f/g = ∞

Growth rate hierarchy (memorize)

1 < log log n < log n < √n < n < n log n < n² < n³ < 2ⁿ < n! < nⁿ

Common sums

Arithmetic: 1 + 2 + ... + n = n(n+1)/2 = Θ(n²)
Squares: 1² + 2² + ... + n² = n(n+1)(2n+1)/6 = Θ(n³)
Geometric (r > 1): 1 + r + r² + ... + rⁿ = (rⁿ⁺¹ − 1)/(r − 1) = Θ(rⁿ)
Geometric (r < 1): converges to 1/(1−r) = Θ(1)
Harmonic: 1 + 1/2 + 1/3 + ... + 1/n = H(n) = Θ(log n)
Log-of-factorial: log(n!) = Θ(n log n) (Stirling)

Master Theorem — T(n) = a·T(n/b) + f(n), c* = log_b(a)

Case 1: f(n) = O(n^(c* − ε)) → Θ(n^(c*))
Case 2: f(n) = Θ(n^(c*) log^k n) → Θ(n^(c*) log^(k+1) n)
Case 3: f(n) = Ω(n^(c* + ε)) & regularity → Θ(f(n))

Standard algorithm complexities

Algorithm	Time (avg)	Time (worst)	Space
Linear search	Θ(n)	Θ(n)	Θ(1)
Binary search	Θ(log n)	Θ(log n)	Θ(1)
Bubble / Insertion / Selection sort	Θ(n²)	Θ(n²)	Θ(1)
Merge sort	Θ(n log n)	Θ(n log n)	Θ(n)
Quick sort	Θ(n log n)	Θ(n²)	Θ(log n)
Heap sort	Θ(n log n)	Θ(n log n)	Θ(1)
Counting / Radix sort	Θ(n + k)	Θ(n + k)	Θ(n + k)
BFS / DFS	Θ(V + E)	Θ(V + E)	Θ(V)
Dijkstra (binary heap)	Θ((V+E) log V)	Θ((V+E) log V)	Θ(V)
Bellman-Ford	Θ(V·E)	Θ(V·E)	Θ(V)
Floyd-Warshall	Θ(V³)	Θ(V³)	Θ(V²)
Hash table lookup	Θ(1)	Θ(n)	Θ(n)
Balanced BST ops	Θ(log n)	Θ(log n)	Θ(n)

Pattern-spotting shortcuts

Halving / doubling → log n
Halving repeatedly, each step is linear → n log n
Two nested loops over n → n²
Try all subsets → 2ⁿ
Try all permutations → n!
Divide-and-conquer, merge in linear time → often n log n
Square-root-shrink → log log n
Amortized over a doubling structure → constant per op

Interview red flags to avoid

Saying "O(n)" when you mean average case but worst case is O(n²) — always clarify.
Forgetting recursion stack in space analysis.
Assuming hash operations are always O(1) without acknowledging worst case.
Using O when you can prove Θ — it makes you look less rigorous.
Missing that log(n!) = Θ(n log n), a classic gotcha.