Big-O Cheat Sheet
A complete time complexity cheat sheet – from the basic Big O notation hierarchy to every major data structure and sorting algorithm. Bookmark it, screenshot it, know it.
Ordered from best to worst performance. For n = 1,000,000 the difference between O(1) and O(n²) is the difference between 1 operation and 1 trillion.
| Notation | Name | Rating | Typical example | Relative cost |
|---|---|---|---|---|
| O(1) | Constant | Excellent | Hash table lookup, array index access, push/pop stack | |
| O(log n) | Logarithmic | Great | Binary search, balanced BST operations, binary heap insert | |
| O(√n) | Square root | Great | Sieve of Eratosthenes inner loop, primality by trial division | |
| O(n) | Linear | Good | Linear search, single loop over array, BFS/DFS traversal | |
| O(n log n) | Linearithmic | Fair | Merge sort, heap sort, most efficient comparison sorts | |
| O(n²) | Quadratic | Bad | Bubble sort, insertion sort, checking every pair | |
| O(n³) | Cubic | Terrible | Naive matrix multiplication, Floyd-Warshall, 3 nested loops | |
| O(2ⁿ) | Exponential | Horrible | Fibonacci (naive recursion), power set enumeration | |
| O(n!) | Factorial | Horrible | Brute-force Travelling Salesman, generating all permutations |
Operations required as n grows from 1 to 100. The gap between O(n log n) and O(n²) becomes enormous, fast.
Average and worst-case time complexities for the most common data structures. Space complexity is O(n) for all unless noted.
| Structure | Average case | Worst case | Space | |||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Access | Search | Insert | Delete | Access | Search | Insert | Delete | |||
| Arrays & Lists | ||||||||||
| Array | O(1) | O(n) | O(n) | O(n) | O(1) | O(n) | O(n) | O(n) | O(n) | |
| Dynamic Array | O(1) | O(n) | O(1)* | O(n) | O(1) | O(n) | O(n) | O(n) | O(n) | |
| Singly Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) | |
| Doubly Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) | |
| Skip List | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | O(n) | O(n) | O(n) | O(n log n) | |
| Stacks, Queues & Heaps | ||||||||||
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) | |
| Queue | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) | |
| Priority Queue (binary heap) | — | O(n) | O(log n) | O(log n) | — | O(n) | O(log n) | O(log n) | O(n) | |
| Hash Tables | ||||||||||
| Hash Table (HashMap) | O(1) | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) | O(n) | O(n) | |
| Trees | ||||||||||
| Binary Search Tree (BST) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | O(n) | O(n) | O(n) | O(n) | |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | |
| Red-Black Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | |
| B-Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | |
| Trie (prefix tree) | O(k) | O(k) | O(k) | O(k) | O(k) | O(k) | O(k) | O(k) | O(n·k) | |
| Binary Heap | — | O(n) | O(log n) | O(log n) | — | O(n) | O(log n) | O(log n) | O(n) | |
| Graphs | ||||||||||
| Adjacency List | — | O(V+E) | O(1) | O(E) | — | O(V+E) | O(1) | O(E) | O(V+E) | |
| Adjacency Matrix | O(1) | O(V²) | O(1) | O(1) | O(1) | O(V²) | O(1) | O(1) | O(V²) | |
* amortized. k = key length. V = vertices, E = edges.
Time and space complexity, stability, and dominant use case for every major sorting algorithm.
| Algorithm | Best | Average | Worst | Space | Stable? | Notes |
|---|---|---|---|---|---|---|
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Fastest in practice; worst case with bad pivot — use randomized |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Guaranteed O(n log n); preferred for linked lists and external sort |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | In-place with guaranteed worst-case; poor cache performance |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | Default in Python and Java; exploits existing order in real data |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | No | Quicksort + heapsort fallback; default in C++ STL |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Educational only; never use on large data |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Minimizes writes; useful when write cost is much higher than read |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Best for small or nearly-sorted arrays; used inside Timsort |
| Shell Sort | O(n log n) | O(n log²n) | O(n²) | O(1) | No | Gap-sequence dependent; practical for medium-sized arrays |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes | Non-comparison sort; k = value range; integer keys only |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | Yes | Beats comparison sorts for integers; k = number of digits |
| Bucket Sort | O(n+k) | O(n+k) | O(n²) | O(n) | Yes | Best for uniformly distributed float data |
Quick reference for graph traversal, searching, string matching, math, dynamic programming, and heap operations.
- BFS / DFSO(V+E)
- Dijkstra (heap)O((V+E) log V)
- Bellman-FordO(VE)
- Floyd-WarshallO(V³)
- Prim's MST (heap)O(E log V)
- Kruskal's MSTO(E log E)
- Topological sortO(V+E)
- Tarjan (SCC)O(V+E)
- Linear searchO(n)
- Binary searchO(log n)
- Jump searchO(√n)
- Interpolation search*O(log log n)
- Exponential searchO(log n)
- Quickselect (avg)O(n)
- Median of mediansO(n)
- Naive searchO(nm)
- KMP searchO(n+m)
- Rabin-KarpO(n+m)
- Boyer-Moore*O(n/m)
- Edit distance (DP)O(nm)
- Longest common subseqO(nm)
- Z-algorithmO(n+m)
- GCD (Euclid)O(log min(a,b))
- Sieve of EratosthenesO(n log log n)
- Primality (trial div.)O(√n)
- Fast exponentiationO(log n)
- Matrix mult. (naive)O(n³)
- Strassen matrix mult.O(n^2.81)
- FFTO(n log n)
- Fibonacci (memoized)O(n)
- 0/1 KnapsackO(nW)
- Longest inc. subseq.O(n log n)
- Coin changeO(nA)
- Matrix chain mult.O(n³)
- All-pairs shortest pathO(V³)
- Build heapO(n)
- InsertO(log n)
- Extract min/maxO(log n)
- Peek min/maxO(1)
- Decrease keyO(log n)
- Find k-th largestO(n + k log n)
* best/average for uniformly distributed input. n = text length, m = pattern length, W = capacity, A = amount.
You can often read the complexity directly from the shape of the code without any math.
Single loop
Each element visited once. Classic for linear scan, finding max/min, summing an array.
Nested loops (same range)
Every pair considered. Bubble sort, naive string matching, checking all pairs.
Halving the input each step
Binary search, balanced tree traversal, binary lifting — anything that halves the search space.
Divide & conquer with merge
log n recursion levels × O(n) merge work per level. Covers most divide-and-conquer.
Exploring all subsets
Two choices at each element → 2ⁿ leaf nodes. Power set, brute-force knapsack.
Exploring all permutations
n choices at root, n-1 at next level … → n! total paths. TSP brute force.
Two pointers / sliding window
Each pointer advances at most n steps total → O(n). Subarray/substring problems.
Naive recursion (no memo)
Overlapping subproblems recomputed from scratch. Add a memo cache → O(n).
Six rules that let you simplify any complexity expression to its canonical form.
Three distinct notations that describe different bounds. In everyday speech, "Big O" usually means the tight bound — which is technically Theta.
O( f )
f(n) grows no faster than g(n). The algorithm takes at most this long. "O(n²)" means it could be faster in some cases but never worse.
Θ( f )
f(n) grows at exactly the same rate as g(n) — both upper and lower bounds match. When someone says "binary search is O(log n)" they almost always mean Θ(log n).
Ω( f )
f(n) grows at least as fast as g(n). "Comparison sorting is Ω(n log n)" means no comparison sort can beat n log n in the worst case.
o( f )
Like Big O but strictly smaller — f grows slower than g, not equal to it. If f is O(n) it could equal O(n); if f is o(n) it must be strictly less than linear.
A practical guide to which complexity is acceptable at a given input size, assuming roughly 10⁸ simple operations per second.
| Input size n | Max safe complexity | Practical examples |
|---|---|---|
| n ≤ 12 | O(n!) | Permutation enumeration, brute-force TSP |
| n ≤ 25 | O(2ⁿ) | Bitmask DP, power set enumeration |
| n ≤ 100 | O(n³) | Floyd-Warshall, matrix chain multiplication |
| n ≤ 1,000 | O(n²) | Insertion sort, naive DP, checking all pairs |
| n ≤ 10,000 | O(n²) (tight) | Still quadratic but watch constant factors carefully |
| n ≤ 100,000 | O(n log n) | Merge sort, segment trees, balanced BSTs |
| n ≤ 1,000,000 | O(n) or O(n log n) | Linear scan, hash table, BFS/DFS, radix sort |
| n ≤ 10⁹ | O(√n) or O(log n) | Binary search, primality check, mathematical queries |
| n > 10⁹ | O(1) or O(log n) | Hash lookup, direct formula, binary search on answer |
The most common mistakes, gotchas, and mental shortcuts for analyzing complexity on the fly.
while (n > 1) n = Math.sqrt(n) loop is O(log log n). Structure matters, not size.
.slice() is O(k). Python in list is O(n) but in set is O(1). sorted() is O(n log n). String concatenation inside a loop in Java or Python is O(n²) — use StringBuilder or join.
Reference compiled for educational use. Complexities reflect standard implementations — actual performance varies with constant factors, cache behavior, language, and hardware.
Use this Big O cheat sheet as a quick reference to understand how algorithms scale with input size and to guide better coding decisions.
From constant time operations to exponential growth, each complexity class highlights performance trade-offs you’ll encounter in real-world development.
This time complexity cheat sheet is great for:
- Optimizing loops
- Choosing data structures
- Preparing for technical interviews
- Keeping these patterns in mind can help you write faster, more efficient code
Bookmark this page and revisit it whenever you need a refresher on time and space complexity fundamentals or want to compare algorithm efficiency at a glance across different scenarios and use cases quickly.