Formula sheet
Every formula from every topic. Type to filter.
📈 Asymptotic Analysis & Recurrences
Order of growth
1 < log log n < log n < √n < n < n log n < n² < n³ < 2ⁿ < n! < nⁿ
Sums
1 + 2 + … + n = n(n + 1)/2; 1 + 2 + 4 + … + 2ᵏ = 2ᵏ⁺¹ − 1; 1 + 1/2 + 1/4 + … < 2; H_n = 1 + 1/2 + … + 1/n = Θ(log n)
Master theorem
T(n) = aT(n/b) + Θ(nᵏ logᵖ n): log_b a > k → Θ(n^(log_b a)); = k → Θ(nᵏ logᵖ⁺¹ n); < k → Θ(nᵏ logᵖ n)
Stirling
log(n!) = Θ(n log n); n! = Θ(√n (n/e)ⁿ)
Log rules
log_a b = log_c b / log_c a, so all log bases differ by a constant factor. 2^(log₂ n) = n
🔀 Sorting & Searching
Comparisons
bubble/selection n(n − 1)/2; insertion: n − 1 (best) to n(n − 1)/2; merge ≈ n log₂ n − n + 1 (worst)
Inversions
insertion-sort shifts = number of inversions; reversed array has n(n − 1)/2
Quick sort
average / best 2T(n/2) + n → Θ(n log n); worst T(n − 1) + n → Θ(n²)
Lower bound
decision tree height ≥ ⌈log₂ n!⌉ = Ω(n log n)
Binary search
worst case ⌊log₂ n⌋ + 1 comparisons; min and max together: ⌈3n/2⌉ − 2
Counting sort / radix
Θ(n + k); radix Θ(d(n + k))
🕸️ Graph Algorithms
Edges
undirected simple: 0 ≤ E ≤ V(V − 1)/2; connected: E ≥ V − 1; directed simple: E ≤ V(V − 1); Σ deg = 2E
BFS / DFS
O(V + E) with adjacency lists; O(V²) with an adjacency matrix
MST
Kruskal O(E log E); Prim O(E log V) heap, O(V²) array; MST has V − 1 edges
Shortest paths
Dijkstra O((V + E) log V); Bellman-Ford O(VE); Floyd-Warshall Θ(V³)
Topological sort
O(V + E); exists iff the graph is a DAG
Edge classes (directed DFS)
back edge ⇔ cycle; forward / cross edges go to a finished vertex
🧩 Algorithm Design: Divide & Conquer, Greedy, DP
Divide & conquer examples
merge sort 2T(n/2) + n; binary search T(n/2) + 1; Strassen 7T(n/2) + n²; Karatsuba 3T(n/2) + n
Greedy
activity selection: sort by earliest finish; fractional knapsack: sort by v/w; Huffman: n − 1 merges
LCS / edit distance
time and space O(mn); c[i][j] = c[i − 1][j − 1] + 1 (match) else max(up, left)
0/1 knapsack
t[i][c] = max(t[i − 1][c], t[i − 1][c − wᵢ] + vᵢ); O(nW)
Matrix chain
m[i][j] = min_k ( m[i][k] + m[k + 1][j] + p[i − 1]p[k]p[j] ); O(n³) time, O(n²) space; (p × q)(q × r) costs pqr
Catalan (parenthesisations)
number of ways to parenthesise n matrices = C(n − 1)
🧮 P, NP & NP-Completeness
Inclusions
P ⊆ NP; NP-complete = NP ∩ NP-hard; if P ≠ NP, then P ∩ NP-complete = ∅
Reduction direction
A ≤ₚ B and B ∈ P ⇒ A ∈ P; A NP-hard and A ≤ₚ B ⇒ B NP-hard
Classic chain
SAT → 3-SAT → Clique ↔ Independent set ↔ Vertex cover; Hamiltonian cycle → TSP
Pairs that differ
2-SAT ∈ P vs 3-SAT NPC; Euler circuit ∈ P vs Hamiltonian NPC; shortest vs longest simple path