Reference shelf

Big-O cheat sheet

Every structure and algorithm, average and worst case, plus space.

Written by Claude Opus 4.8

The whole course as one lookup table: every structure and every algorithm with its cost. Come back to it before an interview, or when you are choosing what to reach for.

How to read these

$n$ is the number of elements; for graphs $V$ and $E$ count vertices and edges, and for strings $m$ is the pattern length and $L$ a key's length. Every bound drops constants and lower-order terms. A dash means the operation is not native to that structure. Insert and delete costs assume you already hold a handle to the position, so they exclude the search to find it.

Data structures, average case

The cost you get in normal use, when hashes spread and trees stay balanced. This is the table to reason with day to day.

Structure	Access	Search	Insert	Delete	Space
Array	$O (1)$	$O (n)$	$O (n)$	$O (n)$	$O (n)$
Dynamic array	$O (1)$	$O (n)$	$O (1)$	$O (n)$	$O (n)$
Linked list	$O (n)$	$O (n)$	$O (1)$	$O (1)$	$O (n)$
Stack	$O (n)$	$O (n)$	$O (1)$	$O (1)$	$O (n)$
Queue	$O (n)$	$O (n)$	$O (1)$	$O (1)$	$O (n)$
Deque	$O (n)$	$O (n)$	$O (1)$	$O (1)$	$O (n)$
Hash table	-	$O (1)$	$O (1)$	$O (1)$	$O (n)$
Binary search tree	$O (lo g n)$	$O (lo g n)$	$O (lo g n)$	$O (lo g n)$	$O (n)$
Balanced BST (AVL, red-black)	$O (lo g n)$	$O (lo g n)$	$O (lo g n)$	$O (lo g n)$	$O (n)$
B-tree	$O (lo g n)$	$O (lo g n)$	$O (lo g n)$	$O (lo g n)$	$O (n)$
Binary heap	-	$O (n)$	$O (lo g n)$	$O (lo g n)$	$O (n)$
Trie	$O (L)$	$O (L)$	$O (L)$	$O (L)$	$O (Σ \cdot N)$
Union-find	-	$O (α (n))$	$O (α (n))$	-	$O (n)$

Dynamic-array insert is amortized O(1) at the end but O(n) at an interior index. Heap search and delete refer to an arbitrary key; its native ops are peek-min O(1) and extract-min O(log n).

Data structures, worst case

The guarantee when adversarial input piles every key into one bucket or skews a plain BST into a list. This is the table to design against.

Structure	Access	Search	Insert	Delete	Space
Array	$O (1)$	$O (n)$	$O (n)$	$O (n)$	$O (n)$
Dynamic array	$O (1)$	$O (n)$	$O (n)$	$O (n)$	$O (n)$
Linked list	$O (n)$	$O (n)$	$O (1)$	$O (1)$	$O (n)$
Stack	$O (n)$	$O (n)$	$O (1)$	$O (1)$	$O (n)$
Queue	$O (n)$	$O (n)$	$O (1)$	$O (1)$	$O (n)$
Deque	$O (n)$	$O (n)$	$O (1)$	$O (1)$	$O (n)$
Hash table	-	$O (n)$	$O (n)$	$O (n)$	$O (n)$
Binary search tree	$O (n)$	$O (n)$	$O (n)$	$O (n)$	$O (n)$
Balanced BST (AVL, red-black)	$O (lo g n)$	$O (lo g n)$	$O (lo g n)$	$O (lo g n)$	$O (n)$
B-tree	$O (lo g n)$	$O (lo g n)$	$O (lo g n)$	$O (lo g n)$	$O (n)$
Binary heap	-	$O (n)$	$O (lo g n)$	$O (lo g n)$	$O (n)$
Trie	$O (L)$	$O (L)$	$O (L)$	$O (L)$	$O (Σ \cdot N)$
Union-find	-	$O (α (n))$	$O (α (n))$	-	$O (n)$

Union-find bounds are amortized over a run; a single find or union with path compression and union by rank is effectively constant. A trie stores up to the alphabet size Sigma pointers per node across N total characters.

The one that pays the rent

A plain BST and a hash table both look O(log n) or O(1) until the input turns against them. A balanced BST buys the guarantee back for ordered data; a good hash function and a bounded load factor buy it back for unordered lookup. Know which worst case you can afford before you pick.

Sorting algorithms

The sorts from the sorting lesson, with the three properties that decide which one fits: whether it is stable, whether it works in place, and how it behaves on already-ordered input.

Algorithm	Best	Average	Worst	Space	Stable
Insertion sort	$O (n)$	$O (n^{2})$	$O (n^{2})$	$O (1)$	Yes
Selection sort	$O (n^{2})$	$O (n^{2})$	$O (n^{2})$	$O (1)$	No
Bubble sort	$O (n)$	$O (n^{2})$	$O (n^{2})$	$O (1)$	Yes
Merge sort	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$	$O (n)$	Yes
Quicksort	$O (n lo g n)$	$O (n lo g n)$	$O (n^{2})$	$O (lo g n)$	No
Heapsort	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$	$O (1)$	No

No comparison sort beats O(n log n) worst case. Quicksort's extra space is the O(log n) recursion stack; its O(n squared) worst case comes from a bad pivot on already-sorted input.

Search, graph, and string algorithms

The rest of the algorithmic toolkit. Graph bounds are in terms of $V$ vertices and $E$ edges; string bounds in text length $n$ and pattern length $m$ .

Algorithm	Time (average)	Time (worst)	Space
Binary search	$O (lo g n)$	$O (lo g n)$	$O (1)$
BFS	$O (V + E)$	$O (V + E)$	$O (V)$
DFS	$O (V + E)$	$O (V + E)$	$O (V)$
Topological sort	$O (V + E)$	$O (V + E)$	$O (V)$
Dijkstra (binary heap)	$O ((V + E) lo g V)$	$O ((V + E) lo g V)$	$O (V)$
Bellman-Ford	$O (V \cdot E)$	$O (V \cdot E)$	$O (V)$
Minimum spanning tree (Kruskal)	$O (E lo g E)$	$O (E lo g E)$	$O (V)$
Minimum spanning tree (Prim)	$O (E lo g V)$	$O (E lo g V)$	$O (V)$
Naive string match	$O (n + m)$	$O (n \cdot m)$	$O (1)$
KMP	$O (n + m)$	$O (n + m)$	$O (m)$
Rabin-Karp	$O (n + m)$	$O (n \cdot m)$	$O (1)$

Dijkstra assumes non-negative weights and a binary-heap priority queue. Bellman-Ford is slower but handles negative edges and flags negative cycles.

Where the numbers come from

Every bound here is derived in the lesson its row links to, from the Big-O rules through the Master Theorem. If a row surprises you, the derivation is one click away.