🐬 Complexity Cheat Sheet

Best known practical bounds for the algorithms in these notes: what each solves, its time and its extra space. $n$ = elements / vertices, $m$ = edges, $q$ = queries, $V$ = value range, $w$ = word size (64), $\alpha$ = inverse Ackermann. Amortized bounds are marked (am.), expected ones (exp.).

What fits in about one second (≈ $10^8$–$10^9$ simple operations): $n\le 11$: $O(n!)$ · $n\le 20$–$25$: $O(2^{n}n)$ · $n\le 40$: $O(2^{n/2})$ · $n\le 500$: $O(n^3)$ · $n\le 5000$: $O(n^2)$ · $n\le 10^5$–$10^6$: $O(n\log n)$, $O(n\sqrt{n})$ up to $10^5$ · $n\le 10^7$–$10^8$: $O(n)$ · larger: $O(\sqrt{n})$, $O(\log n)$, $O(1)$.

Searching, sorting, arrays

Algorithm	Solves	Time	Space
binary search / on answer	monotone predicate	$O(\log V)$ evaluations	$O(1)$
ternary / golden-section search	unimodal function	$O(\log V)$	$O(1)$
merge sort / heap sort / introsort	sorting	$O(n\log n)$	$O(n)$ / $O(1)$ / $O(\log n)$
counting / radix sort	sorting small keys	$O(n+V)$ / $O(n{\log }_{b}V)$	$O(n+V)$
quickselect / median of medians	$k$-th element	$O(n)$ exp. / $O(n)$	$O(1)$
prefix sums, difference arrays	static range sums, offline range adds	$O(n)$ build, $O(1)$ query	$O(n)$
two pointers / sliding window	monotone windows	$O(n)$	$O(1)$
monotonic stack / deque	next greater, window min	$O(n)$	$O(n)$
Kadane	max subarray	$O(n)$	$O(1)$
Boyer–Moore voting	majority	$O(n)$	$O(1)$
inversions (merge sort / Fenwick)	count inversions	$O(n\log n)$	$O(n)$

Data structures

Structure	Operations	Time	Space
hash map (custom hash)	insert / find	$O(1)$ exp.	$O(n)$
std::set / map, treap, splay	ordered set, split / merge	$O(\log n)$ (am. / exp.)	$O(n)$
order-statistics tree (pbds)	$k$-th, rank	$O(\log n)$	$O(n)$
binary heap / pairing heap	push, pop min / meld	$O(\log n)$ / $O(1)$ meld am.	$O(n)$
DSU (union by size + compression)	union, find	$O(\alpha (n))$ am.	$O(n)$
DSU with rollback	undoable union	$O(\log n)$	$O(n)$
sparse table	idempotent range query	$O(n\log n)$ build, $O(1)$ query	$O(n\log n)$
Fenwick tree	prefix sums, point update	$O(\log n)$	$O(n)$
segment tree (lazy)	range update / query	$O(\log n)$	$O(n)$
persistent segment tree	versions, $k$-th in range	$O(\log n)$	$O(n+q\log n)$
segment tree beats	range chmin + sum	$O((n+q)\log n)$ am.	$O(n)$
Li Chao tree	insert line, min at $x$	$O(\log V)$	$O(n)$
wavelet tree / matrix	$k$-th, rank in range	$O(\log V)$	$O(n\log V)$
sqrt decomposition	flexible range ops	$O(\sqrt{n})$	$O(n)$
Mo’s algorithm	offline range queries	$O((n+q)\sqrt{n})$	$O(n)$
binary trie	max xor, xor-$k$-th	$O(\log V)$	$O(n\log V)$
xor basis	span, max xor subset	$O(\log V)$ per insert	$O(\log V)$
van Emde Boas / fast set (64-ary)	successor on integers	$O(\log \log V)$ / $O({\log }_{64}V)$	$O(V)$ / $O(V/w)$
k-d tree	nearest neighbour, range in 2D	$O(\sqrt{n})$ range, $O(\log n)$ NN avg	$O(n)$
bitset	set ops, subset-sum DP	$O(n/w)$	$O(n/w)$

Dynamic programming

Technique	Solves	Time	Space
0/1 knapsack	capacity $W$	$O(nW)$	$O(W)$
bounded knapsack (monotone deque)	multiplicities	$O(nW)$	$O(W)$
LIS (patience)	longest increasing subsequence	$O(n\log n)$	$O(n)$
LCS / edit distance	alignment	$O(nm)$ ($O(nm/w)$ bit-parallel)	$O(\min (n,m))$ with Hirschberg
interval DP (+ Knuth)	merging, optimal BST	$O(n^3)$ ($O(n^2)$)	$O(n^2)$
bitmask DP / Held–Karp	subsets, TSP	$O(2^n{n}^2)$	$O(2^{n}n)$
SOS DP	sums over subsets	$O(2^{n}n)$	$O(2^n)$
profile DP	tilings on $n\times m$	$O(nm{2}^m)$	$O(2^m)$
digit DP	counting numbers $\le N$	$O(\log N\cdot S\cdot 10)$	$O(\log N\cdot S)$
tree DP, rerooting	subtree / all-roots answers	$O(n)$	$O(n)$
tree knapsack	size-limited subtree DP	$O(nk)$	$O(nk)$
convex hull trick / Li Chao	$d{p}_i={\min }_j(a_j{x}_i+b_j)$	$O(n)$ / $O(n\log n)$	$O(n)$
divide and conquer optimization	monotone argmin, $k$ layers	$O(kn\log n)$	$O(n)$
Aliens (WQS)	exactly $k$ items, concave cost	$O(\log V)\cdot$ inner	inner
slope trick	convex piecewise-linear DP	$O(n\log n)$	$O(n)$
SMAWK / LARSCH	totally monotone row minima	$O(n)$	$O(n)$
matrix exponentiation	linear recurrences of order $k$	$O(k^3\log N)$	$O(k^2)$
dynamic DP	tree DP under updates	$O({\log }^{2}n)$ per update	$O(n)$

Graphs

Algorithm	Solves	Time	Space
BFS / DFS / 0-1 BFS	reachability, unweighted / 0-1 shortest paths	$O(n+m)$	$O(n)$
Dijkstra (binary heap)	SSSP, $w\ge 0$	$O(m\log n)$	$O(n+m)$
Dijkstra (array)	dense SSSP	$O(n^2)$	$O(n)$
Bellman–Ford / SPFA	negative weights, negative cycles	$O(nm)$	$O(n)$
Floyd–Warshall	APSP, transitive closure	$O(n^3)$ ($O(n^3/w)$ closure)	$O(n^2)$
Johnson	APSP sparse with negatives	$O(nm\log n)$	$O(n^2)$
topological sort (Kahn / DFS)	DAG order, DAG DP	$O(n+m)$	$O(n)$
Tarjan / Kosaraju SCC, 2-SAT	condensation, satisfiability	$O(n+m)$	$O(n+m)$
bridges, articulation points, BCC	lowlink	$O(n+m)$	$O(n+m)$
dominator tree (Lengauer–Tarjan)	immediate dominators	$O(m\alpha )$	$O(n+m)$
Kruskal / Prim / Borůvka	MST	$O(m\log m)$ / $O(m\log n)$ / $O(m\log n)$	$O(n+m)$
directed MST (Edmonds)	min arborescence	$O(m\log n)$	$O(n+m)$
Hierholzer	Euler path / circuit	$O(n+m)$	$O(n+m)$
Held–Karp	Hamiltonian path / TSP	$O(2^n{n}^2)$	$O(2^{n}n)$
chromatic number (IE)	graph colouring	$O(2^{n}n)$	$O(2^n)$
Yen / Eppstein	$k$ shortest paths	$O(kn(m+n\log n))$ / $O(m+n\log n+k\log k)$	$O(n+m+k)$
offline dynamic connectivity	edge insert / delete	$O(q\log q\log n)$	$O(q\log q)$
matrix-tree theorem	count spanning trees	$O(n^3)$	$O(n^2)$

Flows and matching

Algorithm	Solves	Time	Space
Dinic	max flow	$O(n^{2}m)$; $O(m\sqrt{n})$ unit networks	$O(n+m)$
push–relabel (HLPP + gap)	max flow	$O(n^2\sqrt{m})$	$O(n+m)$
Stoer–Wagner	global min cut	$O(n^3)$ / $O(nm+n^2\log n)$	$O(n^2)$
Karger–Stein	global min cut w.h.p.	$O(n^2{\log }^{3}n)$	$O(n^2)$
Gomory–Hu	all-pairs min cut	$(n-1)\times$ max flow	$O(n+m)$
SSP with potentials	min-cost flow	$O(Fm\log n)$	$O(n+m)$
capacity / cost scaling, network simplex	min-cost flow, any costs	$O(m^2\log U\log n)$ / $O(n^{2}m\log (nC))$ / fast in practice	$O(n+m)$
Hungarian	assignment	$O(n^{2}m)$	$O(nm)$
Kuhn / Hopcroft–Karp	bipartite matching	$O(nm)$ / $O(m\sqrt{n})$	$O(n+m)$
Edmonds’ blossom	general matching	$O(n^3)$	$O(n+m)$
weighted blossom	max-weight general matching	$O(n^3)$	$O(n^2)$
matroid intersection	max common independent set	$O(r{n}^2)$ oracle calls	$O(n)$
Gale–Shapley / Irving	stable marriage / roommates	$O(n^2)$	$O(n^2)$

Trees

Algorithm	Solves	Time	Space
binary lifting	LCA, $k$-th ancestor, path aggregates	$O(n\log n)$ / $O(\log n)$	$O(n\log n)$
Euler tour + sparse table	LCA	$O(n\log n)$ / $O(1)$	$O(n\log n)$
Schieber–Vishkin	LCA	$O(n)$ / $O(1)$	$O(n)$
ladder algorithm	level ancestor	$O(n\log n)$ / $O(1)$	$O(n\log n)$
HLD + segment tree	path update / query	$O({\log }^{2}n)$	$O(n)$
centroid decomposition	all-paths counting, distance index	$O(n\log n)$ (+ per query $O(\log n)$)	$O(n\log n)$
DSU on tree / small to large	subtree queries offline	$O(n\log n)$	$O(n)$
virtual tree	DP on $k$ marked vertices	$O(k\log n)$	$O(k)$
link-cut tree, top tree	dynamic forests	$O(\log n)$ am.	$O(n)$
Euler tour tree	link / cut with subtree sums	$O(\log n)$ exp.	$O(n)$
AHU / tree hashing	tree isomorphism	$O(n\log n)$ / $O(n)$	$O(n)$
Prüfer encode / decode	labelled tree $\leftrightarrow$ sequence	$O(n)$	$O(n)$

Number theory and math

Algorithm	Solves	Time	Space
binary exponentiation	$a^e\mathrm{mod}m$	$O(\log e)$	$O(1)$
Euclid / extended Euclid	gcd, Bézout, inverse	$O(\log \min (a,b))$	$O(1)$
CRT / Garner	combine congruences	$O(k\log M)$ / $O(k^2)$	$O(k)$
Eratosthenes / linear sieve	primes, spf, multiplicative functions	$O(n\log \log n)$ / $O(n)$	$O(n)$
segmented sieve	primes in $[L,R]$	$O((R-L)\log \log R+\sqrt{R})$	$O(\sqrt{R}+R-L)$
Miller–Rabin	64-bit primality	$O(7\log n)$ mulmods	$O(1)$
Pollard–Brent rho	64-bit factorization	$\tilde{O}(n^{1/4})$ exp.	$O(1)$
harmonic lemma / floor-sum blocks	$\sum f(\lfloor n/i\rfloor )$	$O(\sqrt{n})$	$O(1)$
floor sum (AC library)	$\sum \lfloor (ai+b)/c\rfloor$	$O(\log )$	$O(1)$
Du’s sieve / Min_25 / Lucy	prefix sums of $\phi$, $\mu$, primes	$O(n^{2/3})$ / $O(n^{3/4}/\log n)$	$O(n^{2/3})$ / $O(\sqrt{n})$
baby-step giant-step	discrete log	$O(\sqrt{m})$	$O(\sqrt{m})$
Tonelli–Shanks / Cipolla	modular square root	$O({\log }^{2}p)$ / $O(\log p)$	$O(1)$
Lucas / Granville	$\left(\genfrac{}{}{0ex}{}{n}{k}\right)\mathrm{mod}{p}^e$	$O(p^e+\log n)$	$O(p^e)$
Gaussian elimination	systems, rank, determinant, inverse	$O(n^3)$ ($O(n^3/w)$ over GF(2))	$O(n^2)$
characteristic polynomial (Hessenberg)	$\det (xI-A)$	$O(n^3)$	$O(n^2)$
Berlekamp–Massey	minimal recurrence	$O(n^2)$	$O(n)$
Kitamasa / Bostan–Mori	$N$-th term of order-$d$ recurrence	$O(d^2\log N)$ / $O(d\log d\log N)$	$O(d)$

Polynomials

Algorithm	Solves	Time	Space
FFT / NTT	convolution	$O(n\log n)$	$O(n)$
Karatsuba	multiplication without roots of unity	$O(n^{1.585})$	$O(n)$
arbitrary-mod convolution (3 NTT + CRT / split FFT)	convolution mod any $m$	$O(n\log n)$	$O(n)$
Walsh–Hadamard / subset convolution	xor / and / or, ${\sum }_{s\subseteq t}$	$O(n\log n)$ / $O(n{\log }^{2}n)$	$O(n\log n)$
online (relaxed) convolution	$f$ depends on its own prefix	$O(n{\log }^{2}n)$	$O(n)$
Newton iteration	inverse, log, exp, sqrt, power of series	$O(n\log n)$	$O(n)$
multipoint evaluation / interpolation	values at $n$ points	$O(n{\log }^{2}n)$	$O(n\log n)$
Taylor shift	$f(x+c)$	$O(n\log n)$	$O(n)$
composition / compositional inverse	$f(g(x))$	$O(n{\log }^{2}n)$ (Kinoshita–Li)	$O(n)$
half-GCD	polynomial gcd, resultant	$O(n{\log }^{2}n)$	$O(n)$

Strings

Algorithm	Solves	Time	Space
prefix function (KMP) / Z-function	matching, borders, periods	$O(n+m)$	$O(n)$
polynomial hashing	substring equality	$O(n)$ build, $O(1)$ query	$O(n)$
Aho–Corasick	many patterns	$O(\sum |p|\cdot \sigma +n+\text{matches})$	$O(\sum |p|\sigma )$
suffix array (SA-IS / doubling) + Kasai	sorted suffixes, LCP	$O(n)$ / $O(n\log n)$	$O(n)$
suffix automaton	distinct substrings, occurrences	$O(n\sigma )$ or $O(n\log \sigma )$	$O(n\sigma )$
suffix tree (Ukkonen)	substring structure	$O(n)$	$O(n\sigma )$
Manacher	all palindromes	$O(n)$	$O(n)$
eertree	distinct palindromes online	$O(n\log \sigma )$	$O(n\sigma )$
Duval / Booth	Lyndon factorization / min rotation	$O(n)$	$O(1)$
bitset matching (shift-and)	wildcard / small alphabet	$O(nm/w)$	$O(\sigma m/w)$
FFT wildcard matching	patterns with ?	$O(n\log n)$	$O(n)$

Geometry

Algorithm	Solves	Time	Space
Andrew monotone chain	convex hull	$O(n\log n)$	$O(n)$
rotating calipers	diameter, width, antipodal pairs	$O(n)$ after hull	$O(1)$
point in convex polygon	containment	$O(\log n)$	$O(1)$
half-plane intersection	feasible region	$O(n\log n)$	$O(n)$
Minkowski sum	convex polygons	$O(n+m)$	$O(n+m)$
closest pair	nearest pair of points	$O(n\log n)$	$O(n)$
Welzl	minimum enclosing circle	$O(n)$ exp.	$O(n)$
Bentley–Ottmann	all segment intersections	$O((n+k)\log n)$	$O(n+k)$
Delaunay (Bowyer–Watson / divide and conquer)	triangulation, Voronoi	$O(n\log n)$	$O(n)$
3D convex hull	hull of points in space	$O(n\log n)$ exp. ($O(n^2)$ simple)	$O(n)$

Games, search, randomized, numerical

Algorithm	Solves	Time	Space
Sprague–Grundy	impartial game sums	$O(\text{states}\cdot \text{moves})$	$O(\text{states})$
retrograde analysis	games with cycles	$O(n+m)$	$O(n)$
minimax + alpha–beta	game trees	$O(b^{d/2})$ best case	$O(d)$
backtracking with pruning	constraint search	exponential	$O(\text{depth})$
meet in the middle	subset sums, 4-sum	$O(2^{n/2}n)$	$O(2^{n/2})$
dancing links (Algorithm X)	exact cover	exponential, fast in practice	$O(\text{ones})$
Bron–Kerbosch	maximal cliques	$O(3^{n/3})$	$O(n)$
Dreyfus–Wagner	Steiner tree on $k$ terminals	$O(3^{k}n+2^{k}m\log n)$	$O(2^{k}n)$
simulated annealing / local search	heuristic optimisation	user-chosen	$O(n)$
Freivalds	verify $AB=C$	$O(n^2)$ per round	$O(n)$
Newton / bisection / Simpson	roots, integrals	$O(\log (1/\epsilon ))$ / $O(n)$	$O(1)$
simplex	linear programming	exponential worst, fast in practice	$O(nm)$