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 |
| Shell Sort | O(n log n) | O(n^(4/3)) | O(n^(3/2)) | O(1) | No |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes |
| Tim Sort | O(n) | O(n log n) | O(n log n) | O(n) | 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) |
| Dijkstra's | Shortest Path | O((V+E) log V) | O(V) |
| A* Search | Shortest Path | O(E) | O(V) |
| Bellman-Ford | Shortest Path | O(V × E) | 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 | 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) |
| 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) |
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 length · * = amortised