Complexity Cheat Sheet
Operation costs for every major data structure and the time/space of every algorithm on this site, in one place.
Data structure operations
| Structure | Access | Search | Insert | Delete | Notes |
|---|
| Array (static) | O(1) | O(n) | — | — | contiguous, cache-friendly |
| Dynamic array | O(1) | O(n) | O(1)* end, O(n) middle | O(1) end, O(n) middle | *amortized |
| Sorted array | O(1) | O(log n) | O(n) | O(n) | binary search |
| Linked list (singly) | O(n) | O(n) | O(1) at head / after node | O(1) after node | |
| Doubly linked list | O(n) | O(n) | O(1) | O(1) given node | LRU cache |
| Stack / queue / deque | O(1) ends | O(n) | O(1) | O(1) | |
| Hash map / set | — | O(1) avg | O(1) avg | O(1) avg | O(n) worst |
| Balanced BST (map/set) | O(log n) | O(log n) | O(log n) | O(log n) | ordered, floor/ceiling |
| Binary heap | O(1) top | O(n) | O(log n) | O(log n) top | heapify O(n) |
| Trie | — | O(L) | O(L) | O(L) | L = key length |
| Union-Find | — | O(α(n)) | O(α(n)) union | — | α ≈ constant |
| Fenwick tree | — | O(log n) prefix | O(log n) update | — | |
| Segment tree | — | O(log n) range | O(log n) update | — | lazy for range updates |
| Sparse table | — | O(1) range min/max | — | — | static only, O(n log n) build |
Sorting
| Algorithm | Best | Average | Worst | Space | Stable |
|---|
| Insertion | n | n² | n² | 1 | ✓ |
| Selection | n² | n² | n² | 1 | ✗ |
| Bubble | n | n² | n² | 1 | ✓ |
| Merge | n log n | n log n | n log n | n | ✓ |
| Quick | n log n | n log n | n² | log n | ✗ |
| Heap | n log n | n log n | n log n | 1 | ✗ |
| Counting | n + k | n + k | n + k | k | ✓ |
| Radix | d(n + b) | d(n + b) | d(n + b) | n + b | ✓ |
| Timsort (Python, Java objects) | n | n log n | n log n | n | ✓ |
Introsort (C++ std::sort) | n log n | n log n | n log n | log n | ✗ |
Searching and techniques
| Technique | Time | Space |
|---|
| Linear scan | O(n) | O(1) |
| Binary search | O(log n) | O(1) |
| Binary search on answer | O(log(range) · check) | depends |
| Two pointers | O(n) (plus sort) | O(1) |
| Sliding window | O(n) | O(k) for counts |
| Prefix sums | O(n) build, O(1) query | O(n) |
| Monotonic stack / deque | O(n) | O(n) |
| Top-k with heap | O(n log k) | O(k) |
| Quickselect | O(n) avg, O(n²) worst | O(1) |
Graph algorithms
| Algorithm | Time | Space | Use |
|---|
| BFS / DFS | O(V + E) | O(V) | traversal, unweighted shortest path |
| Topological sort (Kahn / DFS) | O(V + E) | O(V) | DAG ordering |
| Dijkstra (binary heap) | O((V + E) log V) | O(V) | non-negative weights |
| 0-1 BFS | O(V + E) | O(V) | weights 0/1 |
| Bellman-Ford | O(V · E) | O(V) | negative weights, hop limits |
| Floyd-Warshall | O(V³) | O(V²) | all pairs |
| Kruskal | O(E log E) | O(V) | MST, sparse |
| Prim (heap / array) | O(E log V) / O(V²) | O(V) | MST, dense |
| Tarjan (bridges, SCC) | O(V + E) | O(V) | critical edges, SCCs |
| Union-Find | O(α(n)) per op | O(V) | dynamic connectivity |
Dynamic programming families
| Family | Typical state | Time |
|---|
| 1D (robber, stairs, decode) | dp[i] | O(n) |
| LIS | dp[i] or tails | O(n²) / O(n log n) |
| Grid paths | dp[r][c] | O(R·C) |
| LCS / edit distance | dp[i][j] | O(m·n) |
| 0/1 & unbounded knapsack | dp[w] | O(n·W) |
| Interval DP | dp[i][j] | O(n³) |
| Tree DP | per node | O(n) |
| Bitmask DP | dp[mask][i] | O(2ⁿ · n²) |
| Digit DP | pos × tight × state | O(digits · 10 · states) |
Backtracking / enumeration
| Enumeration | Count | Time with copying |
|---|
| Subsets | 2ⁿ | O(n · 2ⁿ) |
| Permutations | n! | O(n · n!) |
| Combinations C(n, k) | C(n, k) | O(k · C(n, k)) |
| All submasks of all masks | 3ⁿ | O(3ⁿ) |
Rough operation budgets (≈10⁸ simple ops/sec)
| n | Max complexity |
|---|
| 10 | O(n!) |
| 20 | O(2ⁿ · n) |
| 500 | O(n³) |
| 5,000 | O(n²) |
| 10⁶ | O(n log n) |
| 10⁸ | O(n) |
| 10¹⁸ | O(log n) |
Useful numbers
| Value | Approx |
|---|
| 2¹⁰ | 10³ |
| 2²⁰ | 10⁶ |
| 2³⁰ | 10⁹ |
| 2³¹ − 1 (INT_MAX) | 2.1 × 10⁹ |
| 2⁶³ − 1 (LLONG_MAX) | 9.2 × 10¹⁸ |
| 10! | 3.6 × 10⁶ |
| 12! | 4.8 × 10⁸ |
| 20! | 2.4 × 10¹⁸ |
| log₂(10⁵) | ≈ 17 |
| log₂(10⁹) | ≈ 30 |