In software architecture, performance tuning, and algorithm engineering, mastering the asymptotic time and space bounds (Big-O notation) of core algorithms is essential for making sound engineering trade-offs.
This cheat sheet catalogs 160+ foundational algorithms and data structures across 7 engineering domains, presenting their best, average, and worst-case time complexities, auxiliary space consumption, and core behavioral properties.
🔗 Related Cheat Sheets: Advanced & Esoteric Data Structures Cheat Sheet · Modern Cryptography Algorithms Cheat Sheet · Core AI Algorithms Cheat Sheet · Python Cheat Sheet
1. Classical & Modern Sorting Algorithms
Categorized into comparison-based sorts (theoretical lower bound $\Omega(n \log n)$) and non-comparison linear sorts:
| Algorithm | Best Time | Average Time | Worst Time | Space Complexity | Stable? | Key Characteristics & Production Usage |
|---|---|---|---|---|---|---|
| Bubble Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Yes | Successive adjacent swaps; pedagogical baseline; rarely used in production |
| Selection Sort | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | No | Selects the extremum each pass; at most $n-1$ memory writes |
| Insertion Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Yes | Extremely efficient for small arrays ($n < 32$) or nearly-sorted datasets |
| Binary Insertion Sort | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Yes | Binary search reduces comparisons to $O(n \log n)$, but shifts remain $O(n^2)$ |
| Shell Sort | $O(n \log n)$ | Varies by gap | $O(n^2) \sim O(n^{1.3})$ | $O(1)$ | No | Diminishing increment insertion sort; Sedgewick sequences achieve sub-quadratic bounds |
| Merge Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | Yes | Divide-and-conquer; gold standard for external sorting and linked lists |
| In-Place Merge Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | Yes | Eliminates auxiliary buffer via block rearrangements; higher constant factors |
| Quick Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ | No | In-place partitioning; median-of-three or randomized pivots avoid worst-case quadratic degradation |
| 3-Way Quick Sort | $O(n)$ | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ | No | Partitions into $<, =, >$; optimal for arrays with massive duplicate keys |
| Heap Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | No | Guaranteed in-place $O(n \log n)$ bound; poor CPU cache locality due to non-sequential traversal |
| Introsort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(\log n)$ | No | C++ std::sort standard: QuickSort ➔ HeapSort on deep recursion ➔ InsertionSort on small slices |
| TimSort | $O(n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | Yes | Python list.sort & Java standard: Adapts to natural runs + merge stack |
| pdqsort | $O(n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(\log n)$ | No | Rust slice::sort_unstable & Go standard: Achieves linear time on presorted and duplicate arrays |
| Counting Sort | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | $O(k)$ | Yes | Non-comparison sort; ideal for dense integer keys where range $k = O(n)$ |
| Bucket Sort | $O(n+k)$ | $O(n+k)$ | $O(n^2)$ | $O(n+k)$ | Yes | Partitions uniformly distributed values into buckets; baseline for external large-scale sorts |
| Radix Sort (LSD/MSD) | $O(d(n+k))$ | $O(d(n+k))$ | $O(d(n+k))$ | $O(n+k)$ | Yes | Digit-by-digit bucket passes; optimal for fixed-length strings and 64-bit integer keys |
2. Searching & Selection Algorithms
| Algorithm | Best Time | Average Time | Worst Time | Space Complexity | Operating Precondition |
|---|---|---|---|---|---|
| Linear Search | $O(1)$ | $O(n)$ | $O(n)$ | $O(1)$ | Unordered sequences; linked lists |
| Binary Search | $O(1)$ | $O(\log n)$ | $O(\log n)$ | $O(1)$ | Monotonically sorted array with random access |
| Interpolation Search | $O(1)$ | $O(\log \log n)$ | $O(n)$ | $O(1)$ | Uniformly distributed numerical array |
| Exponential Search | $O(1)$ | $O(\log i)$ | $O(\log i)$ | $O(1)$ | Unbounded or infinite sorted streams (where $i$ is target index) |
| Quickselect (Hoare) | $O(n)$ | $O(n)$ | $O(n^2)$ | $O(\log n)$ | Finds $k$-th smallest element; in-place partition traversal |
| Median of Medians (BFPRT) | $O(n)$ | $O(n)$ | $O(n)$ Strict | $O(\log n)$ | Guarantees worst-case linear selection by choosing a balanced pivot |
3. Graph Theory Algorithms
| Algorithm | Problem Domain | Directed / Undirected | Time Complexity | Auxiliary Space | Key Mechanics & Edge Constraints |
|---|---|---|---|---|---|
| Breadth-First Search (BFS) | Shortest path (Unweighted) | Both | $O(V + E)$ | $O(V)$ | FIFO queue; finds shortest hops in unweighted graphs |
| Depth-First Search (DFS) | Reachability, Cycles | Both | $O(V + E)$ | $O(V)$ | Recursion/stack; computes discovery and finish timestamps |
| Dijkstra (Binary Heap) | Single-Source Shortest Path | Both | $O((V + E) \log V)$ | $O(V)$ | Greedy relaxation; fails on negative-weight edges |
| Bellman-Ford | Single-Source Shortest Path | Both | $O(V \cdot E)$ | $O(V)$ | Relaxes all edges $V-1$ times; detects negative-weight cycles |
| SPFA (Shortest Path Faster) | Single-Source Shortest Path | Both | Average $O(kE)$, Worst $O(VE)$ | $O(V)$ | Queue-optimized Bellman-Ford; vulnerable to adversarial grids |
| Floyd-Warshall | All-Pairs Shortest Path | Both | $O(V^3)$ | $O(V^2)$ | Dynamic programming: $dp[i][j] = \min(dp[i][j], dp[i][k] + dp[k][j])$ |
| Kruskal (Disjoint-Set Union) | Minimum Spanning Tree (MST) | Undirected | $O(E \log E)$ | $O(V)$ | Greedy edge sorting + Union-Find cycle detection; best for sparse graphs |
| Prim (Binary Heap) | Minimum Spanning Tree (MST) | Undirected | $O((V + E) \log V)$ | $O(V)$ | Expands cut frontier greedily from vertex; best for dense graphs |
| Tarjan's SCC | Strongly Connected Components | Directed | $O(V + E)$ | $O(V)$ | Single DFS pass tracking dfn and low linked values on a stack |
| Kosaraju's SCC | Strongly Connected Components | Directed | $O(V + E)$ | $O(V)$ | Double DFS pass traversing the transposed reverse graph $G^T$ |
| Kahn's Topological Sort | Topological Ordering / DAGs | Directed | $O(V + E)$ | $O(V)$ | In-degree queue reduction; detects directed cycles |
| Edmonds-Karp | Maximum Network Flow | Directed | $O(V \cdot E^2)$ | $O(V + E)$ | Ford-Fulkerson using BFS for shortest augmenting paths |
| Dinic's Algorithm | Maximum Network Flow | Directed | $O(V^2 E)$ (Unit networks $O(E \sqrt{V})$) | $O(V + E)$ | Layered residual graphs + blocking flow DFS extensions |
4. String Algorithms & Pattern Matching
| Algorithm | Primary Problem | Preprocessing Time | Matching Time | Auxiliary Space | Core Mechanics |
|---|---|---|---|---|---|
| KMP (Knuth-Morris-Pratt) | Single Pattern Matching | $O(m)$ | $O(n)$ | $O(m)$ | Computes partial match table ($\pi$ / next) avoiding text backtracking |
| Boyer-Moore | Single Pattern Matching | $O(m + \Sigma)$ | Best $O(n/m)$, Worst $O(nm)$ | $O(m + \Sigma)$ | Right-to-left scanning with Bad Character and Good Suffix skip rules |
| Rabin-Karp | Multi-Pattern Matching | $O(m)$ | Average $O(n+m)$, Worst $O(nm)$ | $O(1)$ | Rolling polynomial hash comparison across sliding windows |
| Aho-Corasick (AC Automaton) | Multi-Pattern Dictionary Search | $O(\sum m_i)$ | $O(n + \text{matches})$ | $O(\sum m_i \cdot \Sigma)$ | Combines Trie structure with KMP failure links; standard for keyword filtering |
| Manacher's Algorithm | Longest Palindromic Substring | $O(1)$ | $O(n)$ Strict | $O(n)$ | Centers delimiter padding; mirrors palindrome radii using rightmost boundaries |
| Z-Algorithm (Extended KMP) | Longest Common Prefix ($LCP$) | $O(m)$ | $O(n)$ | $O(n)$ | Computes $Z[i]$ = max prefix matching length starting at suffix $i$ |
5. Fundamental Data Structures Complexity
| Data Structure | Access / Lookup | Search | Insertion | Deletion | Space Complexity |
|---|---|---|---|---|---|
| Array | $O(1)$ | $O(n)$ | $O(n)$ | $O(n)$ | $O(n)$ |
| Singly / Doubly Linked List | $O(n)$ | $O(n)$ | $O(1)$ (At pointer) | $O(1)$ (At pointer) | $O(n)$ |
| Stack / Queue | $O(n)$ | $O(n)$ | $O(1)$ | $O(1)$ | $O(n)$ |
| Hash Table | N/A | Average $O(1)$, Worst $O(n)$ | Average $O(1)$, Worst $O(n)$ | Average $O(1)$, Worst $O(n)$ | $O(n)$ |
| Binary Search Tree (BST) | $O(\log n) \sim O(n)$ | $O(\log n) \sim O(n)$ | $O(\log n) \sim O(n)$ | $O(\log n) \sim O(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)$ |
| Binary Heap | Top $O(1)$ | $O(n)$ | $O(\log n)$ | Pop $O(\log n)$ | $O(n)$ |
| Disjoint-Set Union (DSU) | N/A | Find $O(\alpha(n))$ | Union $O(\alpha(n))$ | N/A | $O(n)$ |
| Segment Tree | Range $O(\log n)$ | Range $O(\log n)$ | Point $O(\log n)$ | N/A | $O(n)$ |
| Fenwick Tree (Binary Indexed) | Prefix $O(\log n)$ | Point $O(\log n)$ | Point Update $O(\log n)$ | N/A | $O(n)$ |
6. Number Theory & Computational Geometry Summary
| Algorithm | Domain | Time Complexity | Auxiliary Space | Key Mechanics |
|---|---|---|---|---|
| Euclidean GCD | Number Theory | $O(\log(\min(a, b)))$ | $O(1)$ | Iterative modulus reduction |
| Binary Exponentiation | Number Theory | $O(\log b)$ | $O(1)$ | Binary decomposition of exponent ($a^b \pmod m$) |
| Linear Sieve (Euler) | Prime Sieving | $O(n)$ Linear | $O(n)$ | Marks composites by their least prime factor strictly once |
| Fast Fourier Transform (FFT) | Polynomials | $O(n \log n)$ | $O(n)$ | Divide-and-conquer using roots of unity; drops polynomial multiplication from $O(n^2)$ |
| Andrew's Monotone Chain | Geometry | $O(n \log n)$ | $O(n)$ | 2D convex hull construction sorting coordinates before upper/lower scans |
| Rotating Calipers | Geometry | $O(n)$ Linear | $O(1)$ | Computes convex polygon diameters and minimum bounding boxes |
| KD-Tree | Spatial Search | Build $O(n \log n)$, Query $O(\log n)$ | $O(n)$ | Recursively splits $K$-dimensional space along alternating median hyperplanes |