Complexity Cheatsheet
Quick-reference time & space complexities for every major algorithm and data structure. Search, filter, and compare at a glance.
Complexity Scale
Best → WorstSorting Algorithms
Comparison of common sorting algorithms
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| 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 |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n + k) | Yes |
| Bucket Sort | O(n + k) | O(n + k) | O(n²) | O(n + k) | Yes |
Searching Algorithms
Time complexity for finding elements
| Algorithm | Best | Average | Worst | Space |
|---|---|---|---|---|
| Linear Search | O(1) | O(n) | O(n) | O(1) |
| Binary Search | O(1) | O(log n) | O(log n) | O(1) |
| Jump Search | O(1) | O(√n) | O(√n) | O(1) |
| Interpolation Search | O(1) | O(log log n) | O(n) | O(1) |
| Exponential Search | O(1) | O(log n) | O(log n) | O(1) |
| Fibonacci Search | O(1) | O(log n) | O(log n) | O(1) |
| Ternary Search | O(1) | O(log₃ n) | O(log₃ n) | O(1) |
| Block Search | O(1) | O(√n) | O(√n) | O(1) |
Graph Algorithms
Traversal, shortest path, and MST algorithms
| Algorithm | Type | Time | Space |
|---|---|---|---|
| BFS (Breadth-First) | Traversal | O(V + E) | O(V) |
| DFS (Depth-First) | Traversal | O(V + E) | O(V) |
| Connected Components | Traversal | O(V + E) | O(V) |
| Dijkstra's | Shortest Path | O((V+E) log V) | O(V) |
| Floyd-Warshall | All-Pairs SP | O(V³) | O(V²) |
| Prim's MST | MST | O((V+E) log V) | O(V) |
| Kruskal's MST | MST | O(E log E) | O(V) |
| Topological Sort (Kahn's) | Ordering | O(V + E) | O(V) |
| Topological Sort (DFS) | Ordering | O(V + E) | O(V) |
Data Structures
Average-case operation complexities
| Structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(n) | O(1) | O(1) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) |
| Queue | O(n) | O(n) | O(1) | O(1) | O(n) |
| Hash Table | N/A | O(1) | O(1) | O(1) | O(n) |
| Binary Search Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| AVL Tree | 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(n) |
| Splay Tree | O(log n)* | O(log n)* | O(log n)* | O(log n)* | O(n) |
| Heap (Min/Max) | O(1) | O(n) | O(log n) | O(log n) | O(n) |
| Trie | O(m) | O(m) | O(m) | O(m) | O(n×m) |
| Segment Tree | O(log n) | O(log n) | O(log n) | N/A | O(n) |
| B-Tree | 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(n) |
Heap-like Structures
Priority-queue variants compared on merge cost
| Structure | Insert | Find Min | Delete Min | Merge | Space |
|---|---|---|---|---|---|
| Binary Heap | O(log n) | O(1) | O(log n) | O(n) | O(n) |
| Binomial Queue | O(1)* | O(log n) | O(log n) | O(log n) | O(n) |
| Fibonacci Heap | O(1) | O(1) | O(log n)* | O(1) | O(n) |
| Leftist Heap | O(log n) | O(1) | O(log n) | O(log n) | O(n) |
| Skew Heap | O(log n)* | O(1) | O(log n)* | O(log n)* | O(n) |
Dynamic Programming
Classic DP problems and their table shapes
| Problem | Time | Space | Pattern |
|---|---|---|---|
| Fibonacci Numbers | O(n) | O(1) | Memoization |
| Making Change | O(n×m) | O(n) | Unbounded knapsack |
| Longest Common Subsequence | O(n×m) | O(n×m) | 2D table |
| 0/1 Knapsack | O(n×W) | O(n×W) | 2D table |
| House Robber | O(n) | O(1) | 1D array |
| Longest Increasing Subsequence | O(n²) | O(n) | 1D array |
| Edit Distance | O(n×m) | O(n×m) | 2D table |
| Matrix Chain Multiplication | O(n³) | O(n²) | Interval DP |
| Maximum Subarray | O(n) | O(1) | Running sum |
String Algorithms
Pattern matching — n = text length, m = pattern length
| Algorithm | Preprocess | Average | Worst | Space |
|---|---|---|---|---|
| KMP String Matching | O(m) | O(n) | O(n + m) | O(m) |
| Rabin-Karp | O(m) | O(n + m) | O(n×m) | O(1) |
| Z-Algorithm | O(n + m) | O(n + m) | O(n + m) | O(n + m) |
Union-Find
Disjoint sets — rank plus path compression reaches O(α(n)) amortised
| Variant | find(x) | union(p, q) | Space |
|---|---|---|---|
| Quick Find | O(1) | O(n) | O(n) |
| Quick Union | O(n) | O(n) | O(n) |
| Path Compression | O(log n)* | O(log n)* | O(n) |
| Union by Rank | O(log n) | O(log n) | O(n) |
Big-O Notation
Describes the upper bound of an algorithm's growth rate — the worst-case scenario as input size grows to infinity.
Time vs Space
Faster algorithms often use more memory. This fundamental trade-off shapes every design decision in algorithm engineering.
Practical Tips
O(n log n) is optimal for comparison-based sorting. Use hash tables for O(1) average-case lookups. Prefer heaps for priority queues.
n = input size · V = vertices · E = edges · k = range/digit count · m = string/key/pattern length · W = knapsack capacity · α = inverse Ackermann · * = amortised