🐬 Algorithms

Major named algorithms, grouped by problem domain, each solving one well-defined problem. For the full alphabetical list of every named algorithm/theorem/structure mentioned anywhere in the notes (much longer, no grouping), see 🐬 Named Algorithms. For the general strategies these are instances of, see 🐬 Paradigms; for cross-cutting tricks, 🐬 Techniques; for the structures they run on, 🐬 Data Structures.

Sorting

Algorithm	Solves	Complexity	Note
Merge sort	stable comparison sort	$O(n\log n)$	Sorting
Quicksort	in-place comparison sort	$O(n\log n)$ expected	Sorting
Counting / radix sort	sort by small-range or fixed-width keys	$O(n+k)$ / $O(nd)$	Sorting

Searching

Algorithm	Solves	Complexity	Note
Binary search (and variants)	find a boundary in a monotone predicate	$O(\log n)$	Binary Search
Ternary / golden-section search	optimum of a unimodal function	$O(\log n)$	Ternary Search

Graph shortest paths

Algorithm	Solves	Complexity	Note
Dijkstra’s algorithm	single-source shortest paths, non-negative weights	$O(m\log n)$	Shortest Paths
Bellman–Ford	single-source shortest paths, negative weights, cycle detection	$O(nm)$	Shortest Paths
Floyd–Warshall	all-pairs shortest paths	$O(n^3)$	Shortest Paths
SPFA	Bellman–Ford with a queue, usually faster, adversarially slow	$O(nm)$ worst case	Shortest Paths
Johnson’s algorithm	all-pairs shortest paths, negative weights allowed	$O(nm\log n)$	Shortest Paths
0-1 BFS	shortest paths, weights in $\{0,1\}$	$O(n+m)$	Shortest Paths
Suurballe’s algorithm	two vertex-disjoint shortest paths	$O(m\log n)$	Shortest Path Techniques
Eppstein’s algorithm	$k$ shortest paths	$O(m\log m+k\log k)$	K Shortest Paths

Graph structure

Algorithm	Solves	Complexity	Note
Kosaraju’s / Tarjan’s SCC	strongly connected components	$O(n+m)$	SCC and 2-SAT
Tarjan’s bridge/articulation-point algorithm	cut edges and cut vertices	$O(n+m)$	Bridges and Biconnectivity
Kahn’s algorithm / DFS topological sort	a topological order of a DAG	$O(n+m)$	DAGs and Topological Sort
Hierholzer’s algorithm	an Eulerian circuit/path	$O(n+m)$	Euler Tours
Lengauer–Tarjan	dominator tree	$O(m\log n)$	Dominator Tree

Minimum spanning trees

Algorithm	Solves	Complexity	Note
Kruskal’s algorithm	MST via sorted edges + DSU	$O(m\log m)$	Minimum Spanning Trees
Prim’s algorithm	MST via a growing frontier	$O(m\log n)$	Minimum Spanning Trees
Borůvka’s algorithm	MST via parallel component-merging rounds	$O(m\log n)$	Minimum Spanning Trees
Edmonds’ algorithm (Chu–Liu/Edmonds)	minimum spanning arborescence (directed)	$O(nm)$	Directed MST

Flows and matching

Algorithm	Solves	Complexity	Note
Ford–Fulkerson / Edmonds–Karp	maximum flow	$O(n{m}^2)$ (Edmonds–Karp)	Max Flow
Dinic’s algorithm	maximum flow	$O(n^{2}m)$, $O(m\sqrt{m})$ unit-cap	Max Flow
Push–relabel	maximum flow	$O(n^2\sqrt{m})$	Push-Relabel
Hopcroft–Karp	maximum bipartite matching	$O(m\sqrt{n})$	Bipartite Matching
Hungarian algorithm (Kuhn–Munkres)	minimum-cost perfect bipartite matching	$O(n^3)$	Assignment Problem
Blossom algorithm	maximum matching in a general graph	$O(n^3)$	General Matching
Gale–Shapley	a stable matching	$O(n^2)$	Stable Matching
Stoer–Wagner	global minimum cut	$O(n^3)$	Global Min Cut

Strings

Algorithm	Solves	Complexity	Note
Knuth–Morris–Pratt (KMP)	single-pattern matching via the prefix function	$O(n+m)$	Prefix Function and Z
Z-algorithm	single-pattern matching via the Z-function	$O(n+m)$	Prefix Function and Z
Manacher’s algorithm	longest palindromic substring at every center	$O(n)$	Palindromes
Aho–Corasick	multi-pattern matching	$O(\sum	p_i
Booth’s algorithm	lexicographically minimal rotation	$O(n)$	String Basics
SA-IS	suffix array construction	$O(n)$	Suffix Array
Ukkonen’s algorithm	online suffix tree construction	$O(n)$	Suffix Tree

Number theory

Algorithm	Solves	Complexity	Note
Extended Euclidean algorithm	$\gcd (a,b)$ and Bézout coefficients	$O(\log \min (a,b))$	GCD and Extended Euclid
Miller–Rabin	probabilistic primality testing	$O(k{\log }^{2}n)$	Primality and Factorization
Pollard’s rho	integer factorization	$O(n^{1/4})$ expected	Primality and Factorization
Tonelli–Shanks	modular square root	$O({\log }^{2}p)$	Modular Square Roots
Baby-step giant-step (BSGS)	discrete logarithm	$O(\sqrt{n})$	Primitive Roots and Discrete Log

Polynomials and transforms

Algorithm	Solves	Complexity	Note
Fast Fourier Transform (FFT)	polynomial multiplication over $\mathbb{C}$	$O(n\log n)$	FFT
Number Theoretic Transform (NTT)	polynomial multiplication mod an NTT-friendly prime	$O(n\log n)$	NTT
Fast Walsh–Hadamard Transform (FWHT)	XOR/AND/OR convolution	$O(n\log n)$	Convolution Variants

Computational geometry

Algorithm	Solves	Complexity	Note
Andrew’s monotone chain	convex hull	$O(n\log n)$	Convex Hull
Rotating calipers	diameter/width of a convex polygon, closest pair of parallel lines, etc.	$O(n)$ after a hull	Rotating Calipers
Bentley–Ottmann	all segment intersections	$O((n+k)\log n)$	Sweep Line
Welzl’s algorithm	minimum enclosing circle	$O(n)$ expected	Minimum Enclosing Circle

Combinatorics

Algorithm	Solves	Complexity	Note
Burnside’s lemma / Pólya enumeration	counting objects up to symmetry	problem-dependent	Burnside and Pólya