Big-O cheat sheet
Time and space complexity of every data structure and algorithm on BytePatterns, from hash tables to Dijkstra, each row linked to its animated lesson.
Updated 78 rows94 lessons linkedPrints cleanly — use your browser's print
How to read it
- n is the input size. Constants and smaller terms are dropped: 3n + 5 is O(n).
- Time is the worst case unless the cell says avg or amortized (cheap on average over a long run of operations, even if one of them is expensive).
- Space is extra space — memory on top of the input, not counting the output. Recursion counts: its call stack is space.
- V and E are vertices and edges; m and n are the two lengths in a two-string or grid problem. Any other letter is defined in its row.
- Constant or logarithmic
- Linear or n log n
- Polynomial
- Exponential or factorial
New to the notation? The Big-O module takes it one idea at a time: What Is Big-O?, O(1) and O(n), O(log n) and Halving, O(n²) and Nested Loops, Comparing Complexities.
Growth orders
The shape matters more than the numbers: an O(n²) solution that is fine at n = 100 is hopeless at n = 100,000. The chart shows the shape for small n; the table shows the step counts at sizes you meet in real constraints.
| Order | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| O(1) constant | 1 | 1 | 1 |
| O(log n) logarithmic | 3.3 | 10 | 19.9 |
| O(n) linear | 10 | 1,000 | 1,000,000 |
| O(n log n) linearithmic | 33.2 | 9,966 | ≈ 107 |
| O(n2) quadratic | 100 | 1,000,000 | ≈ 1012 |
| O(2n) exponential | 1,024 | ≈ 10301 | ≈ 10301029 |
| O(n!) factorial | 3,628,800 | ≈ 102567 | ≈ 105565708 |
| Input limit | Usually fits |
|---|---|
| n ≤ 10 | O(n!) |
| n ≤ 20 | O(2n) |
| n ≤ 500 | O(n3) |
| n ≤ 5,000 | O(n2) |
| n ≤ 106 | O(n log n) |
| n ≤ 107 | O(n) |
| larger | O(log n) or O(1) |
A rule of thumb for a one-second limit, assuming roughly 10⁷–10⁸ simple steps per second. Constant factors and the language move it; the order of the rows does not change.
Data structures
What each operation costs. Card titles link to the lesson that animates it.
Array (dynamic)
- Read / write by index
- O(1)
- Search (unsorted)
- O(n)
- Append at the end
- O(1) amortized
- Insert / delete in the middle
- O(n)
- Space
- O(n)
Every element after the gap has to shift.
Singly linked list
- Reach the k-th node
- O(n)
- Search
- O(n)
- Insert / delete at the head
- O(1)
- Insert / delete after a known node
- O(1)
- Space
- O(n)
See also: Insert and Delete
Doubly linked list
- Push / pop at either end
- O(1)
- Unlink a node you hold
- O(1)
- Search
- O(n)
- Space
- O(n)
The prev pointer is what makes unlinking O(1) — the core of an LRU cache.
Stack
- Push / pop / peek
- O(1)
- Search
- O(n)
- Space
- O(n)
Queue / deque
- Enqueue / dequeue
- O(1)
- Peek front
- O(1)
- Search
- O(n)
- Space
- O(n)
Removing from the front of a plain array is O(n) — use a deque or a ring buffer.
See also: Circular Queue
Hash table (map / set)
- Lookup
- O(1) avgO(n) worst
- Insert
- O(1) avgO(n) worst
- Delete
- O(1) avgO(n) worst
- Space
- O(n)
The worst case is every key in one bucket. No order: iterating sorted costs O(n log n).
See also: When Hashing Fails
Binary heap
- Peek min / max
- O(1)
- Push
- O(log n)
- Pop min / max
- O(log n)
- Build from n items (heapify)
- O(n)
- Search
- O(n)
- Space
- O(n)
See also: Heapify and Sift · Priority Queue
Binary search tree
- Search / insert / delete
- O(h)
- …when balanced
- O(log n)
- …when degenerate (a chain)
- O(n)
- In-order walk
- O(n)
- Space
- O(n)
h is the height. Sorted input builds the chain.
See also: BST Insert and Search · Tree Depth and Balance
Trie
- Insert a word
- O(L)
- Search a word
- O(L)
- Starts-with a prefix
- O(L)
- Space
- O(total characters)
L is the length of the word or prefix — independent of how many words are stored.
See also: Prefix Search · Trie vs Hash Set
Union-find (disjoint set)
- Find / union, both optimisations
- O(α(n)) amortized
- …union by size only
- O(log n)
- …neither
- O(n)
- Space
- O(n)
α is the inverse Ackermann function: at most 4 for any input that fits in memory.
See also: Path Compression · Union by Rank or Size
Graph — adjacency list
- Is there an edge u → v?
- O(deg u)
- Visit all neighbours of u
- O(deg u)
- Add an edge
- O(1)
- Space
- O(V + E)
The default for sparse graphs — which is most interview graphs.
See also: Graph Basics
Graph — adjacency matrix
- Is there an edge u → v?
- O(1)
- Visit all neighbours of u
- O(V)
- Add an edge
- O(1)
- Space
- O(V2)
Worth it only when the graph is dense or V is small.
Sorting
Comparison sorts cannot beat O(n log n) in the worst case; counting and radix sort step around that bound by not comparing.
| Algorithm | Best | Average | Worst | Space | Stable | Notes |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n2) | O(n2) | O(1) | Yes | The O(n) best case needs the stop-when-no-swaps check. |
| Selection sort | O(n2) | O(n2) | O(n2) | O(1) | No | At most n − 1 swaps — its one selling point. |
| Insertion sort | O(n) | O(n2) | O(n2) | O(1) | Yes | Fast on nearly sorted input. |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | |
| Quick sort | O(n log n) | O(n log n) | O(n2) | O(log n) | No | Worst case from repeatedly bad pivots; the stack then grows to O(n). |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Yes | k is the range of values. Integers (or keys) only. |
| Radix sort | O(d·(n + b)) | O(d·(n + b)) | O(d·(n + b)) | O(n + b) | Yes | d digits in base b, one stable pass per digit. |
Searching
| Algorithm | Time | Space | Notes |
|---|---|---|---|
| Linear search | O(n) | O(1) | |
| Binary search | O(log n) | O(1) | Sorted input. Iterative; the recursive version adds O(log n) stack. |
| Search in a rotated sorted array | O(log n) | O(1) | Distinct values. Duplicates can force O(n). |
| Find a peak element | O(log n) | O(1) | |
| Binary search on the answer | O(Clog R) | O(1) | R is the size of the answer range, C the cost of one feasibility check. |
| Search a sorted 2-D matrix (staircase) | O(m + n) | O(1) | m rows, n columns; each step discards a row or a column. |
Array, list and string techniques
| Algorithm | Time | Space | Notes |
|---|---|---|---|
| Two pointers | O(n) | O(1) | |
| Sliding window | O(n) | O(k) | Each element enters and leaves once; k is what the window has to remember. |
| Prefix sums | O(n) buildO(1) per query | O(n) | |
| Subarray sum with a hash map | O(n) | O(n) | |
| Kadane's maximum subarray | O(n) | O(1) | |
| Product of array except self | O(n) | O(1) | Not counting the output array. |
| Dutch national flag (3-way partition) | O(n) | O(1) | |
| Fast & slow pointers (cycle detection) | O(n) | O(1) | |
| Reverse a linked list | O(n) | O(1) | Iterative. Recursion costs O(n) stack. |
| Monotonic stack | O(n) amortized | O(n) | Every element is pushed once and popped at most once. |
| Sliding window maximum (deque) | O(n) | O(k) | |
| KMP string matching | O(n + m) | O(m) | n text, m pattern. |
| Rabin–Karp rolling hash | O(n + m) avgO(n·m) worst | O(1) | Worst case when every window's hash collides. |
| Z-algorithm | O(n + m) | O(n + m) |
Heaps and ordering
| Algorithm | Time | Space | Notes |
|---|---|---|---|
| Top-k with a heap of size k | O(n log k) | O(k) | |
| Top-k frequent with buckets | O(n) | O(n) | |
| K-way merge | O(N log k) | O(k) | N items in total across k sorted lists. |
| Running median (two heaps) | O(log n) addO(1) median | O(n) | |
| Merge intervals | O(n log n) | O(n) | The sort dominates; the sweep is O(n). |
| Meeting rooms (min-heap of end times) | O(n log n) | O(n) |
Graphs and grids
| Algorithm | Time | Space | Notes |
|---|---|---|---|
| Breadth-first search | O(V + E) | O(V) | |
| Depth-first search | O(V + E) | O(V) | Recursive DFS can hit the stack limit on a long path. |
| Shortest path, unweighted (BFS) | O(V + E) | O(V) | |
| Grid flood fill / islands | O(R·C) | O(R·C) | R rows × C columns: each cell visited once. |
| Topological sort (Kahn) | O(V + E) | O(V) | |
| Dijkstra (binary heap) | O((V + E) log V) | O(V) | Non-negative weights only. |
| Bellman–Ford | O(V·E) | O(V) | Handles negative weights and detects negative cycles. |
| Kruskal's MST | O(E log E) | O(V) | Sort the edges, then union-find. |
| Prim's MST (binary heap) | O(E log V) | O(V) | |
| Bipartite check (2-colouring) | O(V + E) | O(V) | |
| Strongly connected components | O(V + E) | O(V) |
Dynamic programming
| Algorithm | Time | Space | Notes |
|---|---|---|---|
| Climbing stairs / Fibonacci-style | O(n) | O(1) | Two rolling variables instead of the table. |
| House robber | O(n) | O(1) | |
| Coin change (fewest coins) | O(n·A) | O(A) | n coin types, A the amount. |
| 0/1 knapsack | O(n·W) | O(W) | W is the capacity; one row, filled right to left. |
| Longest common subsequence | O(m·n) | O(m·n) | O(min(m, n)) space if only the length is needed. |
| Edit distance | O(m·n) | O(m·n) | |
| Longest increasing subsequence (DP) | O(n2) | O(n) | |
| Longest increasing subsequence (tails) | O(n log n) | O(n) | |
| Paths in a grid | O(m·n) | O(n) | One row of the table at a time. |
| Interval DP (matrix-chain order) | O(n3) | O(n2) |
Recursion and backtracking
| Algorithm | Time | Space | Notes |
|---|---|---|---|
| Naive recursive Fibonacci | O(2n) | O(n) | An upper bound; the tight bound is about 1.618ⁿ. |
| Memoized recursion (Fibonacci) | O(n) | O(n) | |
| All subsets | O(n·2n) | O(n) | Not counting the output. |
| All permutations | O(n·n!) | O(n) | Not counting the output. |
| N-queens | O(n!) | O(n) | Upper bound; pruning cuts most of it. |
Math and bits
| Algorithm | Time | Space | Notes |
|---|---|---|---|
| GCD (Euclid) | O(log min(a, b)) | O(1) | |
| Fast exponentiation | O(log n) | O(1) | Iterative squaring; n is the exponent. |
| Sieve of Eratosthenes | O(n log log n) | O(n) | |
| XOR to find the single number | O(n) | O(1) | |
| Count set bits (clear the lowest 1) | O(k) | O(1) | k is the number of 1 bits — at most the word size. |
| Power-of-two check | O(1) | O(1) |
bytepatterns.com/cheatsheets/big-o — every row links to an animated lesson there.