Appendix
Complexity cheat sheet
What runs in time, what to write when two techniques share a row, and which page has the proof and the code.
Traversal & components
| Technique | Time | Note | Page |
|---|---|---|---|
| DFS / BFS on an adjacency list | O(n + m) | O(n + m) | Depth-First SearchBreadth-First Search |
| BFS shortest paths (unweighted) | O(n + m) | O(n) | Breadth-First Search |
| Bridges / articulation points | O(n + m) | low-link values | Connectivity, Bridges, Articulation Points |
| Tarjan / Kosaraju SCC | O(n + m) | condensation DAG | Strongly Connected Components |
| Topological order (Kahn, DFS) | O(n + m) | DAG only | DAGs and Topological Order |
| Cycle detection in a digraph | O(n + m) | three-colour DFS | Cycles: Detection, Extraction, Feedback Sets |
Trees
| Technique | Time | Note | Page |
|---|---|---|---|
| Diameter (two BFS) | O(n) | works with weights | Tree Diameter in Two Passes |
| Tree DP, two states | O(n) | take / not-take | Independent Sets, Cliques, and Treewidth |
| Rerooting | O(n) | answer for every root | Distance, Radius, Eccentricity |
| Subtree = interval (tin/tout) | O(n) pre, O(1) query | Euler tour | Entry/Exit Times and the Euler Tour |
| Binary lifting LCA | pre O(n log n), q O(log n) | O(n log n) memory | LCA by Binary Lifting |
| Euler tour + sparse table LCA | pre O(n log n), q O(1) | RMQ reduction | LCA via Range Minimum Query |
| Tarjan offline LCA | O((n+q) α(n)) | offline, DSU only | Tarjan's Offline LCA |
| HLD path queries | O(log² n) per query | segment tree over chains | Heavy-Light Decomposition |
| Centroid decomposition | O(n log n) | pairs with a distance bound | Centroid Decomposition |
| Small-to-large merging | O(n log² n) | per-subtree sets | Small-to-Large Merging |
| Virtual tree on k marks | O(k log k) | closure has ≤ 2k−1 nodes | Virtual Trees |
Data structures
| Technique | Time | Note | Page |
|---|---|---|---|
| Binary heap / priority_queue | build O(n), ops O(log n) | comparator is inverted | Binary Heap and priority_queue |
| DSU (size + compression) | α(n) amortised | no compression with rollback | Disjoint Set Union (Union–Find) |
| Fenwick (BIT) | add/sum O(log n) | kth by bit lifting | Fenwick Tree (Binary Indexed Tree) |
| Segment tree, iterative | build O(n), query O(log n) | 2n nodes | Segment Tree |
| Segment tree with lazy | O(log n) | push before descending | Segment Tree |
| Sparse table | pre O(n log n), q O(1) | idempotent ops only | Sparse Table and RMQ |
| Trie / xor-trie | O(total length) | max-xor pair in O(B) | Trie (Prefix Tree) and Its Relatives |
Shortest paths
| Technique | Time | Note | Page |
|---|---|---|---|
| Dijkstra + binary heap | O((n + m) log n) | non-negative weights | Dijkstra's Algorithm |
| 0–1 BFS (deque) | O(n + m) | weights in {0, 1} | 0-1 BFS, Dial, Potentials, Johnson |
| Dial / bucket Dijkstra | O(nC + m) | small integer weights | 0-1 BFS, Dial, Potentials, Johnson |
| Bellman–Ford | O(nm) | detects negative cycles | Bellman–Ford and Negative Weights |
| Floyd–Warshall | O(n³) | all pairs, k outermost | Floyd–Warshall |
Counting & matrices
| Technique | Time | Note | Page |
|---|---|---|---|
| Adjacency powers | O(n³ log k) | walks of length k | Counting Walks with Matrix Powers |
| Matrix–Tree theorem | O(n³) | spanning trees mod p | The Matrix–Tree Theorem |
| Linear recurrences (Kitamasa) | O(k² log n) | k-th term of a DP | Linear Recurrences from Graphs and Matrices |
| Bitmask DP (Held–Karp) | O(2ⁿ n²) | n ≤ 20–22 | Held–Karp: Hamilton in O(2ⁿn²) |
Flows & matching
| Technique | Time | Note | Page |
|---|---|---|---|
| Kruskal / Prim / Borůvka MST | O(m log m) | cut property | Minimum Spanning Tree |
| Dinic max flow | O(n²m), O(m√n) unit | min cut from the residual graph | Max Flow: Ford–Fulkerson, Dinic, Push–Relabel |
| Push–relabel | O(n²√m) | dense graphs | Max Flow: Ford–Fulkerson, Dinic, Push–Relabel |
| Min-cost max-flow | O(F · m log n) | potentials keep Dijkstra valid | Min-Cost Max-Flow |
| Min-cut models (closure) | flow | project selection, bipartite cover | Min-Cut Models |
| Kuhn bipartite matching | O(nm) | greedy pre-pass helps | Bipartite Matching (Kuhn's Algorithm) |
| Hopcroft–Karp | O(m√n) | blocking flow per layer | Hopcroft–Karp |
| Kőnig cover / independent set | O(m√n) | min cover = max matching | Kőnig's Theorem and Minimum Covers |
| Hungarian assignment | O(n³) | labels + equality subgraph | The Hungarian Algorithm |
| Blossom (general matching) | O(n³) | odd cycles need contraction | General Matching and Blossoms |
Cycles, colouring, hard problems
| Technique | Time | Note | Page |
|---|---|---|---|
| Hierholzer Euler tour | O(n + m) | emit then reverse | Hierholzer's Linear Algorithm |
| de Bruijn sequence | O(kⁿ) | Euler on (k−1)-mers | De Bruijn Sequences |
| Dirac / Ore Hamiltonicity | O(n²) check | sufficient conditions | When Hamiltonian Cycles Must Exist |
| 2-SAT | O(n + m) | implication graph SCCs | 2-SAT |
| Greedy colouring | O(n + m) | degeneracy + 1 | Graph Colouring |
| Planarity bounds | m ≤ 3n − 6 | Euler's formula | Planarity and Euler's Formula |
| Degree sequence (Havel–Hakimi) | O(n²) | constructs the graph | Degree Sequences and Graphical Sequences |
| Random-walk commute time | O(1) after solve | 2m · effective resistance | Random Walks and Cover Times |
n = vertices, m = edges, α = inverse Ackermann (≤ 4 for any real input). Bounds are worst-case unless marked expected. "Fine" means roughly 10⁸ simple operations per second on a judge machine — see P, NP, and Reductions — What You Actually Need for the reasoning behind the numbers.