Chapter 14 — Key Takeaways

The one-page re-grounding card for algorithms and complexity. Reread this before an exam or interview.

Core definitions (memorize these)

Term One-line definition
Algorithm A finite, definite, effective sequence of steps that halts on every valid input and maps inputs to outputs.
RAM model Idealized machine: each primitive op (read/write a cell, arithmetic, compare, branch) costs 1 unit; count ops vs. input size $n$.
Asymptotic Concerned with behavior as $n \to \infty$; ignores constant factors and small-$n$ behavior.
Worst case $\max$ work over all size-$n$ inputs — a guarantee (the default when unqualified).
Best case $\min$ work over size-$n$ inputs.
Average case Expected work over a stated input distribution.
Polynomial time Running time $O(n^k)$ for a constant $k$ — tractable.
Exponential time Running time $\Omega(c^n)$, $c > 1$ (incl. $n!$) — intractable.

The three notations

Notation Says Formal definition Picture
$f = O(g)$ $f$ grows at most like $g$ $\exists\, c>0, n_0:\ f(n) \le c\,g(n)\ \forall n \ge n_0$ ceiling
$f = \Omega(g)$ $f$ grows at least like $g$ $\exists\, c>0, n_0:\ f(n) \ge c\,g(n)\ \forall n \ge n_0$ floor
$f = \Theta(g)$ $f$ grows exactly like $g$ $f = O(g)$ and $f = \Omega(g)$ sandwich
  • $\Theta$ is symmetric and an equivalence relation on growth rates. $O$ is a preorder (reflexive, transitive, not symmetric).
  • To prove $O$/$\Omega$: produce witnesses $(c, n_0)$ and verify the inequality for all $n \ge n_0$. One valid pair is enough; they are never unique.

Proof skeleton (Big-O from the definition)

Claim: $f(n) = O(g(n))$. 1. Choose $c$ (slightly above the leading coefficient) and $n_0$. 2. Show $f(n) \le c\,g(n)$ for all $n \ge n_0$ (bound lower terms by the leading power). 3. Conclude: witnesses $(c, n_0)$ establish the claim. $\blacksquare$

Template example: $3n + 7 = O(n)$ via $c=4,\, n_0=7$ (since $7 \le n \Rightarrow 3n+7 \le 4n$).

Analysis rules (read Big-O off the code)

Pattern Cost Why
Constant work (index, hash get) $\Theta(1)$ no dependence on $n$
Single loop, $O(1)$ body, $n$ passes $\Theta(n)$ $\sum_{i=1}^n c = cn$
Nested loops, inner depends on outer do the sum e.g. $\sum_{i=0}^{n-1}(n-1-i)=\tfrac{n(n-1)}{2}=\Theta(n^2)$
Nested loops over $n$ and $m$ $\Theta(nm)$ not $n^2$
Halve the range each pass $\Theta(\log n)$ smallest $k$ with $2^k \ge n$
Sequential phases $A$ then $B$ $\Theta(\max)$ sum rule
  • Leading term dominates: $a_d n^d + \dots + a_0 = \Theta(n^d)$. Drop constants and lower terms.
  • Log base is irrelevant: $\log_a n = \Theta(\log_b n)$ — write $O(\log n)$ with no base.

Growth hierarchy (slow → fast; know cold)

$$\Theta(1) \prec \Theta(\log n) \prec \Theta(\sqrt n) \prec \Theta(n) \prec \Theta(n\log n) \prec \Theta(n^2) \prec \Theta(n^3) \prec \Theta(2^n) \prec \Theta(n!)$$

Class Name Typical source Usable up to (rough)
$\Theta(1)$ constant array index, avg hash lookup any $n$
$\Theta(\log n)$ logarithmic binary search billions
$\Theta(n)$ linear max, sum hundreds of millions
$\Theta(n\log n)$ linearithmic merge sort, heapsort tens of millions
$\Theta(n^2)$ quadratic bubble sort, all pairs ~$10^4$
$\Theta(n^3)$ cubic naive matrix multiply ~$10^3$
$\Theta(2^n)$ exponential all subsets, naive Fibonacci ~40
$\Theta(n!)$ factorial all permutations, brute TSP ~12
  • Polynomials beat logs: $\log n = O(n^\varepsilon)$ for any $\varepsilon>0$.
  • Exponentials beat polynomials: $n^k = O(2^n)$ for any $k$.
  • Hardware can't fix exponential: a 1000× faster machine grows a feasible $2^n$ input by only ~10.

Lower bounds (bounding the problem, not an algorithm)

  • A lower bound argues over all possible algorithms. Tool: $\Omega$.
  • Finding the max of $n$ distinct numbers needs $\ge n-1$ comparisons $\Rightarrow \Omega(n)$ (each comparison creates $\le 1$ new "loser"; need $n-1$ losers).
  • Matching an $\Omega$ lower bound with an $O$ algorithm $\Rightarrow$ the algorithm is optimal (max-finding is $\Theta(n)$; the simple scan is optimal).

Decision aid — "what bound / what case do I report?"

  • Reporting an algorithm's speed? → give the worst-case time, as $\Theta$ if you can (tight), else $O$.
  • Claiming a problem is hard / an algorithm is optimal? → prove an $\Omega$ lower bound.
  • Cost depends on input content? → report best / worst / average separately; name the distribution for average.
  • Tractable vs. not? → is it $O(n^k)$ (yes) or $\Omega(c^n)$ (no)?

Common pitfalls (the ones that cost points)

Pitfall Reality
"Two nested loops $\Rightarrow O(n^2)$" Only if inner trip count is $\Theta(n)$. Constant inner $\Rightarrow O(n)$; over $m \Rightarrow O(nm)$.
"$O$ means worst case" Category error. Case = which input; $O/\Omega/\Theta$ = bound shape. They are independent axes.
Confusing $n^2$ and $2^n$ $n^2$ polynomial (tractable); $2^n$ exponential (intractable). At $n=30$: 900 vs. ~$10^9$.
"One line = one operation" list + [x], x in list are $O(n)$. Count what the machine does.
Input size of an integer $N$ is $N$ It's $\log_2 N$ (bit length). $N$ steps is exponential in the size.
Reading "$=$" in $O$ as symmetric It means "$\in$." $O(n) = f(n)$ is meaningless; never flip it.

Toolkit additions (dmtoolkit)

File Function Purpose
complexity.py count_ops(make_input, run, sizes) op count + ratio-to-previous per size
complexity.py doubling_ratios(make_input, run, start, doublings) ratios at $n, 2n, 4n, \dots$ — ratio $\approx 2^k \Rightarrow \Theta(n^k)$

Empirical fingerprint: double $n$ → linear shows ratio ≈ 2, quadratic ≈ 4, cubic ≈ 8, logarithmic ≈ 1.

Connections

  • Builds on: Ch. 9 (algorithm computes a function; floor/ceiling/log), Ch. 11 (loop cost = a sum).
  • Sets up: Ch. 19 (solving the recurrences behind recursive algorithms; Master Theorem), Ch. 28 (complexity of graph traversal, $O(V+E)$), Ch. 37 (P vs. NP — the polynomial/exponential line formalized).