Time and Space Complexity

1Big O, Omega, and Theta

Big O is an asymptotic upper bound: f(n) = O(g(n)) means f grows no faster than a constant times g for large n. Omega (\Omega) is a lower bound — f grows at least as fast as g. Theta (\Theta) is a tight bound: both O and \Omega at once.

Interview and contest speech almost always means worst-case Big O. Saying "this is O(n^2)" does not claim the algorithm is slow on every input; it claims the cost never exceeds a quadratic envelope. A matching \Omega statement is a separate claim.

Figure. Big-O is an upper sandwich, Ω a lower one; Θ means both bounds match the same g up to constants.

Three bound words

1. Big OUpper envelope — "\le a constant times g" for large n.
2. OmegaLower envelope — "\ge a constant times g" for large n.
3. ThetaTight — both envelopes, so f and g grow at the same rate.

2Drop constants and lower-order terms

Asymptotic class keeps only the fastest-growing term and ignores constant multipliers. So 3n^2 + 5n + 7 is O(n^2): the n^2 term dominates, and the factor 3 does not change the class.

The same rule turns O(n^2 + n) into O(n^2) and O(2n \log n) into O(n \log n). Constants matter for wall-clock time; they do not change which Big-O bucket the algorithm sits in.

Figure. At large n the n^2 shape dominates; the leading coefficient and the linear term do not change the Big-O class.

How to reduce

1. Find dominantCompare degrees / growth classes; keep the fastest term.
2. Drop constantsStrip coefficients in front of that term.
3. Drop lowerDiscard every slower-growing addend.

3Common growth order

The standard ladder of common classes is O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!). Each step eventually dominates the previous one as n grows.

Interview answers live on this ladder. Nested loops often land on n^2; binary search and balanced trees land on \log n; merge sort and heap sort land on n \log n; naive subset enumeration lands on 2^n.

Figure. Representative sizes at n = 16 for 1, \log_2 n, n, n \log_2 n, and n^2. Not to scale with 2^n or n! — those need a log axis the vocabulary does not have.

Reading the ladder

1. Polys firstConstant → log → linear → n \log n → quadratic are the everyday interview set.
2. Then explode2^n and n! outgrow every polynomial; they need a different scale to plot honestly.
3. Pick the className the tightest class from the ladder that still upper-bounds the cost.

4Nested loops multiply

Independent nested loops over the same n multiply their iteration counts: an outer n with an inner n is O(n^2). A loop that halves each step contributes an O(\log n) factor instead of a linear one.

A triangular pattern — inner loop runs to i while i runs 1..n — still lands in the quadratic class. The exact sum n(n+1)/2 collapses to O(n^2) after dropping the constant and the linear term; halving the triangle does not change the Big-O bucket.

Figure. Triangle of filled cells for n=5: exactly n(n+1)/2=15 iterations — still O(n^2) after dropping constants.

Count the iterations

1. SumInner passes total 1 + 2 + \cdots + n.
2. Closed formThat sum is n(n+1)/2.
3. AsymptoticDrop the 1/2 and the +n/2 → O(n^2).

Triangular double loop

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

5Master Theorem

For divide-and-conquer recurrences T(n) = aT(n/b) + f(n) with a \ge 1 and b > 1, compare f(n) to n^{\log_b a}. That comparison picks the asymptotic case without fully expanding the recursion tree.

Case 1: f is polynomially smaller than n^{\log_b a} → T(n) = \Theta(n^{\log_b a}). Case 2: f matches that power (up to log factors in the fine print) → an extra \log n appears, as in merge sort. Case 3: f is polynomially larger and a regularity condition holds → T(n) = \Theta(f(n)).

Figure. Master Theorem compares f(n) to n^{\log_b a}: leaf work, balanced, or root-dominated — pick the matching case, not a mash-up.

Apply the theorem

1. Read a, bCount subproblems a and the shrink factor b.
2. Critical powerCompute n^{\log_b a} — the work if leaves dominated.
3. Compare fDecide Case 1 / 2 / 3 from how f sits relative to that power.

6Unrolling a halving recurrence

When the Master Theorem is overkill, unroll. Binary search pays O(1) per level and halves the size: T(n) = T(n/2) + O(1). After k steps the size is n/2^k; stop when that size is 1, so k = \log_2 n and T(n) = O(\log n).

The same unrolling on merge sort's tree — \log n levels, O(n) work per level — recovers O(n \log n) without naming cases. Prefer the theorem when the branching factors are awkward; prefer unrolling when the recursion tree is obvious.

Figure. Each step halves the argument: \log_2 n levels until size 1 — the classic binary-search / merge depth.

Unroll T(n) = T(n/2) + O(1)

1. One stepPay O(1), leave size n/2.
2. k stepsSize n/2^k. Halt at size 1 → k = \log_2 n.
3. Totalk constant-time steps → O(\log n).

7Amortized analysis

Amortized cost averages an operation over a long sequence. A dynamic-array append is O(1) amortized even though a resize is O(n) when it hits: across n appends from empty with doubling, the copy costs 1 + 2 + 4 + \cdots + n = O(n), so the average per append is O(1).

Amortized is not a synonym for average-case over random inputs. It is a worst-case bound on the total of a sequence, divided by the number of operations — a few calls pay a lot; most pay almost nothing; the average stays constant.

Figure. Resize copy counts for eight appends with doubling. The three growth steps sum to 7 — less than one full extra pass over the final length.

Why doubling amortizes

1. Cheap appendIf size < capacity, one write — O(1).
2. ResizeWhen full, copy into a ~2× block — O(\text{capacity}) once.
3. AverageGeometric copies sum to O(n) over n appends → O(1) each amortized.

8Worst, average, amortized, and space

Three time stories can disagree. Hash-map lookup is O(1) average under a good hash and load factor, but O(n) worst case when every key collides. Dynamic-array append is O(1) amortized and O(n) worst on a single call. Always name which story you mean.

Space has its own bound. Extra arrays are obvious; recursion spends O(\text{max call depth}) on the stack even when the heap looks empty. Binary search's recursive form is O(\log n) stack; an iterative rewrite keeps O(1) auxiliary space for the same time class.

Figure. Name the cost model before comparing algorithms — worst-case, average, amortized, and space answer different questions.

Name the cost model

1. WorstCeiling over every input of size n — the interview default for Big O.
2. AverageExpectation under an input (or hash) distribution.
3. AmortizedTotal over a sequence, divided by operation count.
4. SpaceHeap extras plus O(\text{depth}) stack for recursion.