Big-O Complexity Cheat Sheet
Growth order
// fastest → slowest
O(1) < O(log n) < O(sqrt n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)
// about 1e8 simple operations per second
Pick by constraint
n <= 12 → O(n!)
n <= 25 → O(2^n)
n <= 500 → O(n^3)
n <= 5000 → O(n^2)
n <= 1e6 → O(n log n)
n <= 1e8 → O(n)
n >= 1e9 → O(log n) or O(1)
Data structures
array access O(1); search O(n)
hash map get/put O(1) avg, O(n) worst
balanced BST / map / set: O(log n) everything
heap push/pop O(log n), top O(1), heapify O(n)
stack/queue push/pop O(1)
linked list insert at known node O(1), search O(n)
Algorithms
binary search O(log n); sort O(n log n)
BFS/DFS O(V + E); Dijkstra O((V + E) log V)
Floyd–Warshall O(V^3); Bellman–Ford O(V * E)
subsets O(2^n); permutations O(n!)
merge sort space O(n); quick sort worst O(n^2)
Loop patterns
for (i = 1; i < n; i *= 2) // O(log n)
for (i = 1; i * i <= n; i++) // O(sqrt n)
for (i...n) for (j...n) // O(n^2)
for (i...n) for (j = 1; j < n; j *= 2) // O(n log n)
Full Big-O Complexity documentation