Time & Space Complexities
All common complexities in one place – from constant to exponential.
Complexity Classes
Common Runtimes (Fast to Slow)
O(1)– constantO(log n)– logarithmicO(n)– linearO(n log n)– linearithmicO(n²)– quadraticO(2ⁿ)– exponentialO(n!)– factorial
Legend
- Good – fast, efficient
- Moderate – acceptable for medium inputs
- Bad – slow, avoid for large inputs
Data Structure Operations
| Data Structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
| Array (unsorted) | O(1) | O(n) | O(n) | O(n) | O(n) |
| Array (sorted) | O(1) | O(log n) | O(n) | O(n) | O(n) |
| Hash Table | O(1) | O(1) | O(1) | O(1) | O(n) |
| BST (unbalanced) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| BST (unbalanced worst) | O(n) | O(n) | O(n) | O(n) | O(n) |
| AVL / Red-Black | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Heap | O(1) | O(n) | O(log n) | O(log n) | O(n) |
| Stack | O(1) | O(n) | O(1) | O(1) | O(n) |
| Queue | O(1) | O(n) | O(1) | O(1) | O(n) |
| Linked List | O(n) | O(n) | O(1) | O(1) | O(n) |
Sorting Algorithms
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| 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 |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n + k) | Yes |
Graph Algorithms
| Algorithm | Time Complexity | Space Complexity |
|---|---|---|
| DFS / BFS | O(V + E) | O(V) |
| Dijkstra (array) | O(V²) | O(V) |
| Dijkstra (heap) | O((V + E) log V) | O(V) |
| Bellman-Ford | O(VE) | O(V) |
| Floyd-Warshall | O(V³) | O(V²) |
| Kruskal (MST) | O(E log E) | O(V) |
| Prim (MST) | O(E log V) | O(V) |
| Topological Sort | O(V + E) | O(V) |
Common Patterns & Runtimes
Algorithm Patterns
- Binary Search – O(log n)
- Two Pointers – O(n)
- Sliding Window – O(n)
- Merge Sort – O(n log n)
- Dynamic Programming – O(n²) (typical)
- Backtracking – O(2ⁿ)
Input Size Guidelines
- O(1) – any input
- O(log n) – n ≤ 10⁹
- O(n) – n ≤ 10⁷
- O(n log n) – n ≤ 10⁶
- O(n²) – n ≤ 10⁴
- O(2ⁿ) – n ≤ 20
- O(n!) – n ≤ 10
Space Complexity Cheatsheet
- O(1) – in‑place, no extra space Bubble · Insertion · Selection · Heap Sort
- O(log n) – recursion stack Quick Sort · Binary Search
- O(n) – linear extra space Merge Sort · Counting · BFS/DFS
- O(n²) – matrix or table Floyd-Warshall · DP tables
- O(nk) – k factors Radix Sort · Bucket Sort
📌 Quick Reference
Best to worst:
Remember: Space is often a trade‑off. Faster algorithms usually use more memory.
Worst‑case matters – always consider the upper bound for safety.
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)Remember: Space is often a trade‑off. Faster algorithms usually use more memory.
Worst‑case matters – always consider the upper bound for safety.