Time Complexity Cheat Sheet
Quick reference for Big-O notation and algorithm complexity
Complexity Overview
Big-O notation describes the upper bound of an algorithm's growth rate. Here's how common complexities compare:
O(1)
Constant
O(log n)
Logarithmic
O(n)
Linear
O(n log n)
Linearithmic
O(n^2)
Quadratic
O(2^n)
Exponential
Quick Rule
For n = 10^6 (1 million), O(n) takes ~1 second, O(n^2) takes ~10^6 seconds (11 days). Always aim for O(n log n) or better for large inputs.
Data Structures
Array / Vector
| Operation | Average | Worst |
|---|---|---|
| Access by index | O(1) | O(1) |
| Search | O(n) | O(n) |
| Insert at end | O(1)* | O(n) |
| Insert at start | O(n) | O(n) |
| Delete | O(n) | O(n) |
*Amortized for vector
Linked List
| Operation | Average | Worst |
|---|---|---|
| Access by index | O(n) | O(n) |
| Search | O(n) | O(n) |
| Insert at head | O(1) | O(1) |
| Insert at position | O(n) | O(n) |
| Delete (with ref) | O(1) | O(1) |
Stack / Queue
| Operation | Average | Worst |
|---|---|---|
| Push / Enqueue | O(1) | O(1) |
| Pop / Dequeue | O(1) | O(1) |
| Top / Front | O(1) | O(1) |
| Search | O(n) | O(n) |
Hash Table (unordered_map)
| Operation | Average | Worst |
|---|---|---|
| Insert | O(1) | O(n) |
| Search | O(1) | O(n) |
| Delete | O(1) | O(n) |
Worst case occurs with hash collisions
Binary Search Tree (map/set)
| Operation | Average | Worst |
|---|---|---|
| Insert | O(log n) | O(log n) |
| Search | O(log n) | O(log n) |
| Delete | O(log n) | O(log n) |
| Min / Max | O(log n) | O(log n) |
C++ map/set use Red-Black Trees (balanced)
Heap (priority_queue)
| Operation | Time |
|---|---|
| Push | O(log n) |
| Pop (extract max/min) | O(log n) |
| Top (peek) | O(1) |
| Build heap | O(n) |
Sorting Algorithms
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Quick Sort | O(n log n) | O(n log n) | O(n^2) | O(log n) | No |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) | No |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes |
C++ STL Uses Introsort
std::sort() uses Introsort (Quick + Heap + Insertion), guaranteeing O(n log n) worst case. std::stable_sort() uses Merge Sort.
Searching Algorithms
| Algorithm | Time | Space | Requirement |
|---|---|---|---|
| Linear Search | O(n) | O(1) | None |
| Binary Search | O(log n) | O(1) | Sorted array |
| Hash Table Lookup | O(1) avg | O(n) | Hash function |
| BST Search | O(log n) | O(1) | Balanced tree |
Graph Algorithms
| Algorithm | Time | Space | Use Case |
|---|---|---|---|
| DFS | O(V + E) | O(V) | Path finding, cycle detection |
| BFS | O(V + E) | O(V) | Shortest path (unweighted) |
| Dijkstra | O((V+E) log V) | O(V) | Shortest path (positive weights) |
| Bellman-Ford | O(V * E) | O(V) | Shortest path (negative weights) |
| Floyd-Warshall | O(V^3) | O(V^2) | All-pairs shortest path |
| Topological Sort | O(V + E) | O(V) | DAG ordering |
| Union-Find | O(alpha(n)) | O(n) | Disjoint sets, MST |
Quick Tips for Interviews
Common Constraints
- n <= 10: O(n!) or O(2^n) is okay (brute force)
- n <= 20: O(2^n) backtracking
- n <= 500: O(n^3) is okay
- n <= 5000: O(n^2) is okay
- n <= 10^6: O(n log n) or O(n) needed
- n <= 10^8: O(n) or O(log n) needed
Space-Time Tradeoffs
- HashMap: Trade O(n) space for O(1) lookup
- Memoization: Trade space for avoiding recomputation
- Precomputation: Trade initialization time for query speed