The one-page reference sheet (memorize cold)

◈ 4 cards

Every complexity, the growth hierarchy, the master-theorem card, and the proof-technique catalog on a single page — the facts you should be able to reproduce from memory before you walk in.

How to use this lesson

The exam is open-book, so you will not be graded on recall of a table. But if you have to look up the complexity of BUILD-MAX-HEAP mid-problem, you have already lost time you needed for the reasoning. Treat everything below as the layer you make automatic, so the open book is for the derivations, not the facts. Drill the recall questions until they are instant.

Complexity of every algorithm in the course

Sorting (n elements):

Algorithm	Best	Average	Worst	Space	Stable?	In-place?
Insertion sort	Θ(n)	Θ(n²)	Θ(n²)	Θ(1)	yes	yes
Merge sort	Θ(n lg n)	Θ(n lg n)	Θ(n lg n)	Θ(n)	yes	no
Heapsort	Θ(n lg n)	Θ(n lg n)	Θ(n lg n)	Θ(1)	no	yes
Quicksort	Θ(n lg n)	Θ(n lg n)	Θ(n²)	Θ(lg n)	no	yes
Counting sort	Θ(n+k)	Θ(n+k)	Θ(n+k)	Θ(n+k)	yes	no
Radix sort	Θ(d(n+k))	Θ(d(n+k))	Θ(d(n+k))	Θ(n+k)	yes	no
Bucket sort	Θ(n)	Θ(n)	Θ(n²)	Θ(n)	yes	no

Selection: RANDOMIZED-SELECT expected Θ(n); median-of-medians SELECT worst-case Θ(n).

Data-structure operations:

Structure	Search	Insert	Delete	Notes
Sorted array	Θ(lg n)	Θ(n)	Θ(n)	binary search to find
Hash table (chaining)	Θ(1+α) exp.	Θ(1)	Θ(1)	worst Θ(n)
BST (unbalanced)	Θ(h)	Θ(h)	Θ(h)	h up to n−1
Red-black tree	Θ(lg n)	Θ(lg n)	Θ(lg n)	h ≤ 2 lg(n+1)
Binary heap	—	Θ(lg n)	Θ(lg n)	MAX = Θ(1); BUILD = Θ(n)
Union-find	—	—	—	m ops in Θ(m·α(n))

Graph algorithms (V vertices, E edges):

Algorithm	Time	Handles	Notes
BFS / DFS	Θ(V+E)	unweighted	BFS = fewest edges; DFS = timestamps
Topological sort	Θ(V+E)	DAG only	DFS by decreasing finish
Kruskal (MST)	Θ(E lg V)	undirected	sort edges + union-find
Prim (MST)	Θ(E lg V)	undirected	heap keyed by edge to tree
Bellman-Ford	Θ(VE)	negative edges	detects negative cycle
DAG shortest path	Θ(V+E)	DAG, neg OK	relax in topo order
Dijkstra	Θ((V+E) lg V)	nonneg only	greedy + min-heap
Floyd-Warshall	Θ(V³)	all-pairs, neg	DP; k-loop outermost
Edmonds-Karp	Θ(VE²)	flow	BFS augmenting paths

The growth hierarchy (rank cold)

$Θ (1) ≺ Θ (l g n) ≺ Θ (n) ≺ Θ (n) ≺ Θ (n l g n) ≺ Θ (n^{2}) ≺ Θ (n^{3}) ≺ Θ (2^{n}) ≺ Θ (n!) ≺ Θ (n^{n})$

Rules: any polylog loses to any positive polynomial ( $l g^{b} n = o (n^{a})$ ); any polynomial loses to any exponential ( $n^{b} = o (c^{n})$ , $c > 1$ ); and $l g (n!) = Θ (n l g n)$ .

The master theorem card

For $T (n) = a T (n / b) + f (n)$ with watershed $W = n^{l o g_{b} a}$ :

Case 1 — $f = O (n^{l o g_{b} a - ε})$ ⟶ $T = Θ (W)$ . (leaves win)
Case 2 — $f = Θ (n^{l o g_{b} a} l g^{k} n)$ , $k \geq 0$ ⟶ $T = Θ (W l g^{k + 1} n)$ . (tie, add a log)
Case 3 — $f = Ω (n^{l o g_{b} a + ε})$ and $a f (n / b) \leq c f (n)$ , $c < 1$ ⟶ $T = Θ (f)$ . (root wins)

Gap (no case): $f$ and $W$ differ by only a logarithmic factor (e.g. $2 T (n /2) + n / l g n$ ).

The proof-technique catalog

Technique	Used for	The move
Loop invariant	iterative correctness	init / maintenance / termination
Substitution	prove a recurrence bound	guess, then induct with a fixed constant
Recursion tree	guess a recurrence bound	sum cost per level
Exchange argument	greedy is optimal	swap OPT toward the greedy choice, no worse
Cut-and-paste	optimal substructure (DP)	a better subsolution would improve OPT ⇒ contradiction
Decision tree	comparison-sort lower bound	≥ n! leaves ⇒ height Ω(n lg n)
Reduction (≤ₚ)	NP-hardness	map a known-hard problem TO the new one
Lower-bound comparison	approximation ratio	bound OPT below, compare the algorithm to that bound

Sorting, worst case only — the row you actually need under time pressure.

Rank these cold. The bracket is the line between tractable and not.