AlgorithmsTime Complexity Cheatsheet
📊 Time Complexity Cheatsheet
Quick reference for Big O notation, algorithm complexities, and performance characteristics.
Big O Notation Reference
| Notation | Name | Description | Examples |
|---|---|---|---|
| O(1) | Constant | Fixed time regardless of input size | Array access, hash lookup, stack push/pop |
| O(log n) | Logarithmic | Time grows logarithmically with input | Binary search, balanced BST operations |
| O(n) | Linear | Time grows proportionally to input | Linear search, array traversal, string comparison |
| O(n log n) | Linearithmic | Combination of linear and logarithmic | Merge sort, heap sort, quick sort (avg) |
| O(n²) | Quadratic | Time grows quadratically | Bubble sort, insertion sort, nested loops |
| O(2ⁿ) | Exponential | Time doubles with each input addition | Fibonacci (naive), tower of Hanoi |
| O(n!) | Factorial | Time grows factorially | Permutations, traveling salesman (naive) |
Growth Rate Comparison
| n | O(1) | O(log n) | O(n) | O(n log n) | O(n²) | O(2ⁿ) |
|---|---|---|---|---|---|---|
| 10 | 1 | 3 | 10 | 30 | 100 | 1,024 |
| 100 | 1 | 7 | 100 | 700 | 10,000 | 1.27×10³⁰ |
| 1,000 | 1 | 10 | 1,000 | 10,000 | 1,000,000 | — |
| 10,000 | 1 | 13 | 10,000 | 130,000 | 100M | — |
Common Algorithm Complexities
| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Array Access | O(1) | O(1) | O(1) | O(1) |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) |
| Linear Search | O(1) | O(n) | O(n) | O(1) |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) |
| BFS/DFS (Graph) | O(V+E) | O(V+E) | O(V+E) | O(V) |
| Dijkstra | O(V+E log V) | O(V+E log V) | O(V+E log V) | O(V) |
| Hash Table | O(1) | O(1) | O(n) | O(n) |
| BST Operations | O(log n) | O(log n) | O(n) | O(1) |
💡 Quick Tips
- 1. Always consider input constraints when choosing algorithms. n ≤ 20 may allow O(2ⁿ), but n ≥ 10⁶ needs O(n) or better.
- 2. O(n log n) is often considered the "gold standard" for sorting - much faster than O(n²) for large inputs.
- 3. Space-time tradeoff: sometimes using O(n) extra space can reduce time complexity significantly (e.g., hash tables).
- 4. Best case complexity is rarely useful - focus on average and worst-case performance.
- 5. Constants matter! O(100n) is still O(n), but an O(n) algorithm with high constant may be slower than O(n log n) for practical inputs.