Search, Graphs & Complexity
Algorithms Cheat Sheet
Design and Analysis of Algorithms on one page: notations, recurrences, the Master Theorem, every algorithm's complexity, technique selection and exam favourites.
Asymptotic notations
| Notation | Definition (for n ≥ n₀) | Meaning |
|---|---|---|
| f = O(g) | f(n) ≤ c·g(n) | upper bound |
| f = Ω(g) | f(n) ≥ c·g(n) | lower bound |
| f = Θ(g) | c₁·g(n) ≤ f(n) ≤ c₂·g(n) | tight bound |
| f = o(g) | f/g → 0 | strictly smaller |
| f = ω(g) | f/g → ∞ | strictly larger |
Growth: 1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n! < nⁿ
Master Theorem: T(n) = aT(n/b) + f(n)
| Compare f(n) with n^(log_b a) | Result |
|---|---|
| f smaller by a polynomial factor | Θ(n^(log_b a)) |
| f equal (up to logᵏ) | Θ(n^(log_b a) · log n) |
| f larger by a polynomial factor (+ regularity) | Θ(f(n)) |
Common recurrences
| Recurrence | Solution | Example |
|---|---|---|
| T(n) = T(n/2) + 1 | Θ(log n) | binary search |
| T(n) = 2T(n/2) + n | Θ(n log n) | merge sort |
| T(n) = T(n − 1) + n | Θ(n²) | quick sort worst case |
| T(n) = 2T(n − 1) + 1 | Θ(2ⁿ) | Tower of Hanoi |
| T(n) = 3T(n/2) + n | Θ(n^1.585) | Karatsuba |
| T(n) = 7T(n/2) + n² | Θ(n^2.81) | Strassen |
Algorithm complexities
| Algorithm | Technique | Time |
|---|---|---|
| Binary search | D&C | O(log n) |
| Merge sort | D&C | O(n log n) |
| Quick sort | D&C | O(n log n) avg, O(n²) worst |
| Heap sort | heap | O(n log n) |
| Activity selection | greedy | O(n log n) |
| Fractional knapsack | greedy | O(n log n) |
| Huffman coding | greedy | O(n log n) |
| Kruskal | greedy + union-find | O(E log E) |
| Prim | greedy + heap | O(E log V) |
| Dijkstra | greedy + heap | O((V + E) log V) |
| Bellman–Ford | DP | O(VE) |
| Floyd–Warshall | DP | O(V³) |
| 0/1 knapsack | DP | O(nW) |
| LCS | DP | O(mn) |
| Matrix chain | DP | O(n³) |
| BFS / DFS / topological sort | traversal | O(V + E) |
| N-Queens, subset sum | backtracking | exponential |
| KMP | string matching | O(n + m) |
Which technique?
| Clue in the problem | Try |
|---|---|
| split in halves, combine answers | divide and conquer |
| locally best choice is provably safe | greedy |
| overlapping subproblems, "count the ways", "minimum/maximum of" | dynamic programming |
| find all arrangements, satisfy constraints | backtracking |
| optimise over an exponential search space | branch and bound |
| problem is NP-hard and n is large | approximation or heuristics |
Exam favourites
- Define algorithm; properties; loop invariant for insertion sort.
- Prove 3n² + 2n = Θ(n²) by finding c₁, c₂, n₀.
- Solve recurrences with the Master Theorem and recursion trees.
- Trace merge sort and quick sort partition; best/worst cases.
- Activity selection, fractional knapsack, job sequencing tables.
- Huffman tree and codes; average code length.
- Kruskal and Prim on a given graph; Dijkstra table.
- 0/1 knapsack, LCS and matrix-chain tables with traceback.
- Floyd–Warshall matrices D⁰ … Dⁿ.
- N-Queens state-space tree; subset sum.
- KMP prefix function for a pattern.
- P, NP, NP-complete, NP-hard with examples; Cook's theorem.
Final check: mixed revision
4 questions · pick an answer to check it instantly
- 1
Solve T(n) = 2T(n/2) + n log n.
Extended case 2 of the Master Theorem with k = 1. - 2
Which algorithm finds a minimum spanning tree?
Kruskal and Prim find MSTs; Dijkstra and Bellman–Ford find shortest paths. - 3
Which technique does the LCS algorithm use?
Overlapping subproblems L[i][j] are stored in a table. - 4
A problem that is in NP and to which every NP problem reduces is...
NP-complete = NP-hard and in NP.