Algorithms and Data Structures Cheatsheet

NOTE: Source/Credit https://algs4.cs.princeton.edu/cheatsheet/

We summarize the performance characteristics of classic algorithms and data structures for sorting, priority queues, symbol tables, and graph processing.

We also summarize some of the mathematics useful in the analysis of algorithms, including commonly encountered functions, useful formulas and appoximations, properties of logarithms, order-of-growth notation, and solutions to divide-and-conquer recurrences.



Sorting. The table below summarizes the number of compares for a variety of sorting algorithms, as implemented in this textbook. It includes leading constants but ignores lower-order terms.
ALGORITHM	CODE	IN PLACE	STABLE	BEST	AVERAGE	WORST	REMARKS
selection sort	Selection.java	✔		½ n 2	½ n 2	½ n 2	n exchanges;
quadratic in best case
insertion sort	Insertion.java	✔	✔	n	¼ n 2	½ n 2	use for small or
partially-sorted arrays
bubble sort	Bubble.java	✔	✔	n	½ n 2	½ n 2	rarely useful;
use insertion sort instead
shellsort	Shell.java	✔		n log3 n	unknown	c n 3/2	tight code;
subquadratic
mergesort	Merge.java		✔	½ n lg n	n lg n	n lg n	n log n guarantee;
stable
quicksort	Quick.java	✔		n lg n	2 n ln n	½ n 2	n log n probabilistic guarantee;
fastest in practice
heapsort	Heap.java	✔		n †	2 n lg n	2 n lg n	n log n guarantee;
in place
† n lg n if all keys are distinct

Priority queues. The table below summarizes the order of growth of the running time of operations for a variety of priority queues, as implemented in this textbook. It ignores leading constants and lower-order terms. Except as noted, all running times are worst-case running times.
DATA STRUCTURE	CODE	INSERT	DEL-MIN	MIN	DEC-KEY	DELETE	MERGE
array	BruteIndexMinPQ.java	1	n	n	1	1	n
binary heap	IndexMinPQ.java	log n	log n	1	log n	log n	n
d-way heap	IndexMultiwayMinPQ.java	logd n	d logd n	1	logd n	d logd n	n
binomial heap	IndexBinomialMinPQ.java	1	log n	1	log n	log n	log n
Fibonacci heap	IndexFibonacciMinPQ.java	1	log n †	1	1 †	log n †	1
† amortized guarantee

Symbol tables. The table below summarizes the order of growth of the running time of operations for a variety of symbol tables, as implemented in this textbook. It ignores leading constants and lower-order terms.
worst case	average case
DATA STRUCTURE	CODE	SEARCH	INSERT	DELETE	SEARCH	INSERT	DELETE
sequential search
(in an unordered list)	SequentialSearchST.java	n	n	n	n	n	n
binary search
(in a sorted array)	BinarySearchST.java	log n	n	n	log n	n	n
binary search tree
(unbalanced)	BST.java	n	n	n	log n	log n	sqrt(n)
red-black BST
(left-leaning)	RedBlackBST.java	log n	log n	log n	log n	log n	log n
AVL
AVLTreeST.java	log n	log n	log n	log n	log n	log n
hash table
(separate-chaining)	SeparateChainingHashST.java	n	n	n	1 †	1 †	1 †
hash table
(linear-probing)	LinearProbingHashST.java	n	n	n	1 †	1 †	1 †
† uniform hashing assumption

Graph processing. The table below summarizes the order of growth of the worst-case running time and memory usage (beyond the memory for the graph itself) for a variety of graph-processing problems, as implemented in this textbook. It ignores leading constants and lower-order terms. All running times are worst-case running times.

PROBLEM	ALGORITHM	CODE	TIME	SPACE
path	DFS	DepthFirstPaths.java	E + V	V
shortest path (fewest edges)	BFS	BreadthFirstPaths.java	E + V	V
cycle	DFS	Cycle.java	E + V	V
directed path	DFS	DepthFirstDirectedPaths.java	E + V	V
shortest directed path (fewest edges)	BFS	BreadthFirstDirectedPaths.java	E + V	V
directed cycle	DFS	DirectedCycle.java	E + V	V
topological sort	DFS	Topological.java	E + V	V
bipartiteness / odd cycle	DFS	Bipartite.java	E + V	V
connected components	DFS	CC.java	E + V	V
strong components	Kosaraju–Sharir	KosarajuSharirSCC.java	E + V	V
strong components	Tarjan	TarjanSCC.java	E + V	V
strong components	Gabow	GabowSCC.java	E + V	V
Eulerian cycle	DFS	EulerianCycle.java	E + V	E + V
directed Eulerian cycle	DFS	DirectedEulerianCycle.java	E + V	V
transitive closure	DFS	TransitiveClosure.java	V (E + V)	V 2
minimum spanning tree	Kruskal	KruskalMST.java	E log E	E + V
minimum spanning tree	Prim	PrimMST.java	E log V	V
minimum spanning tree	Boruvka	BoruvkaMST.java	E log V	V
shortest paths (nonnegative weights)	Dijkstra	DijkstraSP.java	E log V	V
shortest paths (no negative cycles)	Bellman–Ford	BellmanFordSP.java	V (V + E)	V
shortest paths (no cycles)	topological sort	AcyclicSP.java	V + E	V
all-pairs shortest paths	Floyd–Warshall	FloydWarshall.java	V 3	V 2
maxflow–mincut	Ford–Fulkerson	FordFulkerson.java	E V (E + V)	V
bipartite matching	Hopcroft–Karp	HopcroftKarp.java	V ½ (E + V)	V
assignment problem	successive shortest paths	AssignmentProblem.java	n 3 log n	n 2

Commonly encountered functions. Here are some functions that are commonly encountered when analyzing algorithms.
FUNCTION	NOTATION	DEFINITION
floor	⌊x⌋	largest integer not greater than x
ceiling	⌈x⌉	smallest integer not smaller than x
binary logarithm	lgx  or  log2x	y such that 2y=x
natural logarithm	lnx  or  logex	y such that ey=x
common logarithm	log10x	y such that 10y=x
iterated binary logarithm	lg∗x	0 if x≤1;lg∗(lgx) otherwise
harmonic number	Hn	1+1/2+1/3+…+1/n
factorial	n!	1×2×3×…+n
binomial coefficient	(nk)	n!k!(n−k)!

Useful formulas and approximations. Here are some useful formulas for approximations that are widely used in the analysis of algorithms.
Harmonic sum:   1+1/2+1/3+…+1/n∼lnn
Triangular sum:   1+2+3+…+n=n(n+1)/2∼n2/2
Sum of squares:   12+22+32+…+n2∼n3/3
Geometric sum:   If r≠1, then 1+r+r2+r3+…+rn=(rn+1−1)/(r−1)
Geometric sum (r = 1/2):   1+1/2+1/4+1/8+…+1/2n∼2
Geometric sum (r = 2):   1+2+4+8+16+…+n=2n−1∼2n, when n is a power of 2
Stirling's approximation:   lg(n!)=lg1+lg2+lg3+…+lgn∼nlgn
Exponential:   (1−1/n)n∼1/e
Binomial coefficients:   (nk)∼nk/k! when k is a small constant
Approximate sum by integral:   If f(x) is a monotonically increasing function, then ∫n0f(x)dx≤∑i=1nf(i)≤∫n+11f(x)dx

Properties of logarithms.
Definition:   logba=c means ab=c. We refer to b as the base of the logarithm.
Special cases:   logbb=1,logb1=0
Inverse of exponential:   blogbx=x
Product:   logb(x×y)=logbx+logby
Division:   logb(x÷y)=logbx−logby
Finite product:   logb(x1×x2×…×xn)=logbx1+logbx2+…+logbxn
Changing bases:   logbx=logcx/logcb
Rearranging exponents:   xlogby=ylogbx
Exponentiation:   logb(xy)=ylogbx

Definitions for order-of-growth notations.
NAME	NOTATION	DESCRIPTION	DEFINITION
Tilde	f(n)∼g(n)	f(n) is equal to g(n) asymptotically
(including constant factors)	limn→∞f(n)g(n)=1
Big Oh	f(n) is O(g(n))	f(n) is bounded above by g(n) asymptotically
(ignoring constant factors)	there exist constants c>0 and n0≥0 such that 0≤f(n)≤c⋅g(n) for all n≥n0
Big Omega	f(n) is Ω(g(n))	f(n) is bounded below by g(n) asymptotically
(ignoring constant factors)	g(n) is O(f(n))
Big Theta	f(n) is Θ(g(n))	f(n) is bounded above and below by g(n) asymptotically
(ignoring constant factors)	f(n) is both O(g(n)) and Ω(g(n))
Little oh	f(n) is o(g(n))	f(n) is dominated by g(n) asymptotically
(ignoring constant factors)	limn→∞f(n)g(n)=0
Little omega	f(n) is ω(g(n))	f(n) dominates g(n) asymptotically
(ignoring constant factors)	if g(n) is o(f(n))

Common orders of growth.
NAME	NOTATION	EXAMPLE	CODE FRAGMENT
Constant	O(1)	array access
arithmetic operation
function call	
op();
Logarithmic	O(logn)	binary search in a sorted array
insert in a binary heap
search in a red–black tree	
for (int i = 1; i <= n; i = 2*i)
   op();
Linear	O(n)	sequential search
grade-school addition
BFPRT median finding	
for (int i = 0; i < n; i++)
   op();
Linearithmic	O(nlogn)	mergesort
heapsort
fast Fourier transform	
for (int i = 1; i <= n; i++)
   for (int j = i; j <= n; j = 2*j)
      op();
Quadratic	O(n2)	enumerate all pairs
insertion sort
grade-school multiplication	
for (int i = 0; i < n; i++)
   for (int j = i+1; j < n; j++)
      op();
Cubic	O(n3)	enumerate all triples
Floyd–Warshall
grade-school matrix multiplication	
for (int i = 0; i < n; i++)
   for (int j = i+1; j < n; j++)
      for (int k = j+1; k < n; k++)
         op();
Polynomial	O(nc)	ellipsoid algorithm for LP
AKS primality algorithm
Edmond's matching algorithm
Exponential	2O(nc)	enumerating all subsets
enumerating all permutations
backtracing search

Properties of order-of-growth notations.
Reflexivity:   f(n) is O(f(n)).
Constants:   If f(n) is O(g(n)) and c>0, then c⋅f(n) is O(g(n))).
Products:   If f1(n) is O(g1(n)) and f2(n) is O(g2(n))), then f1(n)⋅f2(n) is O(g1(n)⋅g2(n))).
Sums:   If f1(n) is O(g1(n)) and f2(n) is O(g2(n))), then f1(n)+f2(n) is O(max{g1(n),g2(n)}).
Transitivity:   If f(n) is O(g(n)) and g(n) is O(h(n)), then f(n) is O(h(n)).
Polynomials:   Let f(n)=a0+a1n+…+adnd with ad>0. Then, f(n) is Θ(nd).
Logarithms and polynomials:   logbn is O(nd) for every b>0 and every d>0.
Exponentials and polynomials:   nd is O(rn) for every r>0 and every d>0.
Factorials:   n! is 2Θ(nlogn).
Limits:   If limn→∞f(n)g(n)=c for some constant 0<c<∞, then f(n) is Θ(g(n)).
Limits:   If limn→∞f(n)g(n)=0, then f(n) is O(g(n)) but not Θ(g(n)).
Limits:   If limn→∞f(n)g(n)=∞, then f(n) is Ω(g(n)) but not O(g(n)).

Here are some examples.

FUNCTION	o(n2)	O(n2)	Θ(n2)	Ω(n2)	ω(n2)	∼2n2	∼4n2
log2n	✔	✔					
10n+45	✔	✔					
2n2+45n+12		✔	✔	✔		✔	
4n2−2n−−√		✔	✔	✔			✔
3n3				✔	✔		
2n				✔	✔		

Divide-and-conquer recurrences. For each of the following recurrences we assume T(1)=0 and that n/2 means either ⌊n/2⌋ or ⌈n/2⌉.
RECURRENCE	T(n)	EXAMPLE
T(n)=T(n/2)+1	∼lgn	binary search
T(n)=2T(n/2)+n	∼nlgn	mergesort
T(n)=T(n−1)+n	∼12n2	insertion sort
T(n)=2T(n/2)+1	∼n	tree traversal
T(n)=2T(n−1)+1	∼2n	towers of Hanoi
T(n)=3T(n/2)+Θ(n)	Θ(nlog23)=Θ(n1.58...)	Karatsuba multiplication
T(n)=7T(n/2)+Θ(n2)	Θ(nlog27)=Θ(n2.81...)	Strassen multiplication
T(n)=2T(n/2)+Θ(nlogn)	Θ(nlog2n)	closest pair

Master theorem. Let a≥1, b≥2, and c>0 and suppose that T(n) is a function on the non-negative integers that satisfies the divide-and-conquer recurrence
T(n)=aT(n/b)+Θ(nc)
with T(0)=0 and T(1)=Θ(1), where n/b means either ⌊n/b⌋ or either ⌈n/b⌉.
If c<logba, then T(n)=Θ(nlogba)
If c=logba, then T(n)=Θ(nclogn)
If c>logba, then T(n)=Θ(nc)
Remark: there are many different versions of the master theorem. The Akra–Bazzi theorem is among the most powerful.