Big-O Complexity Documentation
Time and space complexity of every common data structure and algorithm, and how to pick one from the constraints.
One page with the time and space complexity of every common data structure and algorithm, how to work out the complexity of your own code, and which complexity fits a problem's constraints. For the concepts from scratch read Time & Space Complexity (Big-O).
1. What Big-O Means
Big-O describes how the running time (or memory) of an algorithm grows as the input size n grows, ignoring constants and smaller terms.
3n² + 5n + 20→ O(n²)2n + log n→ O(n)- Constants are dropped: O(2n) = O(n), O(n/2) = O(n).
| Notation | Meaning |
|---|---|
| O (Big-O) | upper bound — "grows no faster than" (usually the worst case) |
| Ω (Omega) | lower bound — "grows at least as fast as" |
| Θ (Theta) | tight bound — both |
Best, average and worst case are different questions: quicksort is Θ(n log n) on average but O(n²) in the worst case.
2. Growth Rates Compared
| Big-O | Name | n = 10 | n = 1,000 | n = 1,000,000 | Example |
|---|---|---|---|---|---|
| O(1) | constant | 1 | 1 | 1 | array index, hash lookup |
| O(log n) | logarithmic | 3 | 10 | 20 | binary search |
| O(√n) | square root | 3 | 32 | 1,000 | primality by trial division |
| O(n) | linear | 10 | 1,000 | 10⁶ | one loop over the array |
| O(n log n) | linearithmic | 33 | 10⁴ | 2 × 10⁷ | merge sort, heap sort |
| O(n²) | quadratic | 100 | 10⁶ | 10¹² ❌ | nested loops, bubble sort |
| O(n³) | cubic | 1,000 | 10⁹ | ❌ | Floyd–Warshall, naive matrix multiply |
| O(2ⁿ) | exponential | 1,024 | ❌ | ❌ | all subsets |
| O(n!) | factorial | 3.6 × 10⁶ | ❌ | ❌ | all permutations |
Order: 1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n!
3. Constraints → Expected Complexity
A typical judge does about 10⁸ simple operations per second. Use n from the problem to guess the intended solution:
| n up to | Acceptable | Typical technique |
|---|---|---|
| 10–12 | O(n!), O(n · 2ⁿ) | permutations, brute force |
| 20–25 | O(2ⁿ), O(n · 2ⁿ) | subsets, bitmask DP, meet in the middle |
| 100–500 | O(n³) | Floyd–Warshall, interval DP |
| 1,000–5,000 | O(n²) | 2-D DP, nested loops |
| 10⁵–10⁶ | O(n log n) or O(n) | sorting, heaps, binary search, two pointers, prefix sums |
| 10⁷–10⁸ | O(n) with small constant | linear scan, sieve |
| 10⁹–10¹⁸ | O(log n) or O(1) | binary search on answer, maths, fast power |
4. Data Structure Operations
| Structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
| Array (static) | O(1) | O(n) | O(n) | O(n) | O(n) |
Dynamic array (vector, ArrayList, Python list) |
O(1) | O(n) | O(1) amortised at end, O(n) middle | O(1) end, O(n) middle | O(n) |
| Sorted array | O(1) | O(log n) | O(n) | O(n) | O(n) |
| Singly linked list | O(n) | O(n) | O(1) at head / known node | O(1) at head | O(n) |
| Doubly linked list | O(n) | O(n) | O(1) at known node | O(1) at known node | O(n) |
| Stack / Queue / Deque | O(n) | O(n) | O(1) | O(1) | O(n) |
Hash table (unordered_map, HashMap, dict) |
— | O(1) avg, O(n) worst | O(1) avg | O(1) avg | O(n) |
Balanced BST (map, set, TreeMap) |
O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Unbalanced BST | O(n) worst | O(n) worst | O(n) worst | O(n) worst | O(n) |
Binary heap (priority_queue, heapq) |
top O(1) | O(n) | O(log n) | pop O(log n) | O(n) |
| Trie (key length L) | — | O(L) | O(L) | O(L) | O(total chars × alphabet) |
| Segment tree / Fenwick tree | — | query O(log n) | update O(log n) | — | O(n) |
| Disjoint set union (path compression + rank) | — | find ≈ O(α(n)) ≈ O(1) | union ≈ O(1) | — | O(n) |
Building a heap from an array with heapify is O(n), not O(n log n).
5. Sorting Algorithms
| Algorithm | Best | Average | Worst | Space | Stable | Notes |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | ✅ | best case with the "no swaps" check |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | ❌ | fewest swaps (n − 1) |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | ✅ | great for small / nearly sorted data |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ | linked lists, external sorting |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | ❌ | fastest in practice with random pivot |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ | in-place, guaranteed n log n |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(k) | ✅ | small integer range k |
| Radix sort | O(d(n + b)) | O(d(n + b)) | O(d(n + b)) | O(n + b) | ✅ | d digits, base b |
| Bucket sort | O(n + k) | O(n + k) | O(n²) | O(n) | ✅ | uniformly distributed input |
| Tim sort (Python, Java objects) | O(n) | O(n log n) | O(n log n) | O(n) | ✅ | merge + insertion sort |
Intro sort (C++ std::sort) |
O(n log n) | O(n log n) | O(n log n) | O(log n) | ❌ | quick + heap + insertion |
Comparison-based sorting can't beat Ω(n log n) in the worst case. More: Sorting Algorithms.
6. Searching & Graph Algorithms
| Algorithm | Time | Space |
|---|---|---|
| Linear search | O(n) | O(1) |
| Binary search | O(log n) | O(1) iterative |
| BFS / DFS (adjacency list) | O(V + E) | O(V) |
| BFS / DFS (adjacency matrix) | O(V²) | O(V²) |
| Topological sort (Kahn / DFS) | O(V + E) | O(V) |
| Dijkstra (binary heap) | O((V + E) log V) | O(V) |
| Bellman–Ford | O(V · E) | O(V) |
| Floyd–Warshall | O(V³) | O(V²) |
| Prim (binary heap) | O(E log V) | O(V) |
| Kruskal (sort + DSU) | O(E log E) | O(V) |
| 0-1 BFS | O(V + E) | O(V) |
| Kosaraju / Tarjan (SCC) | O(V + E) | O(V) |
7. Other Classic Algorithms
| Algorithm | Time |
|---|---|
| Sieve of Eratosthenes | O(n log log n) |
| GCD (Euclid) | O(log min(a, b)) |
| Fast exponentiation | O(log n) |
| KMP / Z-algorithm string matching | O(n + m) |
| Rabin–Karp | O(n + m) average |
| Kadane (max subarray) | O(n) |
| Sliding window / two pointers | O(n) |
| Prefix sums: build / query | O(n) / O(1) |
| LIS (patience sorting + binary search) | O(n log n) |
| LCS / edit distance | O(n · m) |
| 0/1 knapsack | O(n · W) |
| N-Queens backtracking | O(n!) |
| Generate all subsets | O(n · 2ⁿ) |
| Generate all permutations | O(n · n!) |
8. How to Analyse Your Code
Loops
for (int i = 0; i < n; i++) {} // O(n)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {} // O(n²)
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++) {} // n(n+1)/2 → O(n²)
for (int i = 1; i < n; i *= 2) {} // O(log n)
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j *= 2) {} // O(n log n)
for (int i = 1; i * i <= n; i++) {} // O(√n)
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j += i) {} // n/1 + n/2 + … → O(n log n) (harmonic series)
Sequential blocks add (keep the largest): O(n) + O(n²) = O(n²). Nested blocks multiply.
Recursion — total work = (number of calls) × (work per call), or use a recurrence:
| Recurrence | Result | Example |
|---|---|---|
| T(n) = T(n − 1) + O(1) | O(n) | factorial, linked-list recursion |
| T(n) = T(n − 1) + O(n) | O(n²) | selection sort recursive |
| T(n) = T(n/2) + O(1) | O(log n) | binary search |
| T(n) = 2T(n/2) + O(n) | O(n log n) | merge sort |
| T(n) = 2T(n/2) + O(1) | O(n) | tree traversal |
| T(n) = 2T(n − 1) + O(1) | O(2ⁿ) | naive Fibonacci, subsets |
Master theorem for T(n) = a·T(n/b) + O(nᵈ):
- d > log_b a → O(nᵈ)
- d = log_b a → O(nᵈ log n)
- d < log_b a → O(n^(log_b a))
Amortised analysis: a dynamic array occasionally doubles (O(n)), but n pushes cost O(n) total → O(1) amortised per push.
9. Space Complexity
Count extra memory the algorithm uses (input usually not counted):
- A few variables → O(1).
- A new array of size n / a hash map of n items → O(n).
- A 2-D DP table n × m → O(n · m) (often reducible to O(m) with rolling rows).
- Recursion uses the call stack: depth d → O(d) space (DFS on a skewed tree → O(n); balanced → O(log n)).
10. Cheat Sheet & References
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)
References