Big O Notation Cheat Sheet — Algorithm Complexity Reference
Big O notation is the universal language for comparing algorithm efficiency. This guide covers the 7 most important complexity classes and 28 algorithms — with practical advice on when each matters for your code.
Why Big O Notation Matters
When you write a sorting function for 10 items, almost any algorithm works. But at 10 million items, the difference between O(n log n) and O(n²) is roughly 500 million operations versus 100 trillion — the difference between milliseconds and weeks.
Big O notation abstracts away hardware differences and describes how an algorithm scales. Use the Big O Complexity Cheat Sheet to filter and compare algorithms by category.
The 7 Complexity Classes You Need to Know
| Notation | Name | Example | n = 1,000,000 |
|---|---|---|---|
| O(1) | Constant | Hash map lookup | 1 op |
| O(log n) | Logarithmic | Binary search | ~20 ops |
| O(n) | Linear | Linear search | 1M ops |
| O(n log n) | Linearithmic | Merge sort | ~20M ops |
| O(n²) | Quadratic | Bubble sort | 1T ops |
| O(2ⁿ) | Exponential | Fibonacci naive | Impossible |
| O(n!) | Factorial | Brute-force TSP | Impossible |
Sorting Algorithm Complexity
Sorting is where Big O matters most in practice. The right algorithm choice depends on data size, whether data is nearly sorted, and whether stability matters.
| Algorithm | Best | Average | Worst | Space | Stable? |
|---|---|---|---|---|---|
| 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(n²) | O(log n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes |
Quick Sort vs Merge Sort
Both average O(n log n), but Quick Sort typically runs 2–3× faster in practice due to better cache locality. The tradeoff: Quick Sort degrades to O(n²) on already-sorted data with a naive pivot. Modern implementations use median-of-three pivoting to avoid this.
Merge Sort guarantees O(n log n) worst case and is stable — but requires O(n) extra space. This is why it is preferred for linked lists and external sorting (data larger than RAM).
Why Insertion Sort still matters
Insertion Sort is O(n²) average, but it is O(n) for nearly-sorted data and has minimal overhead. This is why Python's Timsort and Java's Arrays.sort use insertion sort for small sub-arrays (typically n < 32) — the constant factors dominate at small sizes.
Data Structure Operation Complexity
| Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(n) | O(1) | O(1)* |
| Hash Table | N/A | O(1) | O(1) | O(1) |
| BST (balanced) | O(log n) | O(log n) | O(log n) | O(log n) |
| Stack / Queue | O(n) | O(n) | O(1) | O(1) |
*Linked list deletion is O(1) if you already have the node reference — O(n) to find the node first.
Advanced Workflows for Interview Prep
The "amortized" trick
Dynamic array (ArrayList/vector) append is O(n) when the array resizes — but since each element can only trigger one resize, the amortized cost is O(1). Interview questions often test whether you know the difference between worst-case and amortized complexity.
Space-time trade-offs
Heap Sort achieves O(n log n) time with O(1) extra space — the most space-efficient comparison sort. But it has poor cache performance compared to Quick Sort or Merge Sort, which is why it is rarely used in practice despite its theoretical advantage.
Lower bound on comparison sorting
No comparison-based sorting algorithm can do better than O(n log n) in the worst case. This is a mathematical proof based on the decision tree model — there are n! possible orderings, and each comparison eliminates half. Counting Sort and Radix Sort break this limit by not using comparisons, but only work for restricted input types.
Common Interview Questions
What is the best case for Quick Sort?
O(n log n) — when the pivot always splits the array into equal halves. This happens with a good pivot selection strategy (random pivot or median-of-three).
Why is hash table lookup O(1) amortized but not always?
Hash collisions degrade performance. In the worst case (all keys hash to the same bucket), lookup becomes O(n). Good hash functions and load factor management (typically < 0.75) keep average performance O(1). Python dicts maintain a load factor below 2/3.
What graph algorithms have O(V + E) complexity?
Breadth-First Search (BFS) and Depth-First Search (DFS) both run in O(V + E) where V is vertices and E is edges. Each vertex and edge is visited at most once. Dijkstra's shortest path is O((V + E) log V) with a binary heap.
Explore the Interactive Cheat Sheet
Filter by category and search for specific algorithms in the Big O Complexity Cheat Sheet — 28 algorithms with colour-coded complexities.
Open Big O Cheat Sheet