Beyond classical algorithms and elementary data structures lies the domain of extreme-scale data systems, multi-dimensional optimization, and theoretical computational limits: succinct compact data structures, pruning heuristics, parallel sorting networks, and complexity lower-bound conjectures.
This cheat sheet catalogs 70+ advanced items across 5 specialized domains: succinct data structures, competitive programming techniques, hardware sorting networks, theoretical complexity bounds, and humorous esoteric sorting algorithms.
🔗 Related Cheat Sheets: Algorithms & Data Structures Complexity Master Cheat Sheet · Modern Cryptography Algorithms Cheat Sheet · Core AI Algorithms Cheat Sheet
1. Advanced & Succinct Data Structures
| Data Structure | Core Operation Time Complexity | Space Complexity | Mathematical Foundation & Mechanics | Production Applications |
|---|---|---|---|---|
| van Emde Boas Tree (vEB Tree) | All operations (Insert, Delete, Predecessor) $O(\log \log U)$ | $O(U)$ (Hashable to $O(n)$) | Recursively splits universe $U$ into high/low bits ($\sqrt{U}$ clusters), beating the comparison lower bound | High-performance priority queues over fixed, bounded integer universes |
| Fusion Tree | Search $O(\log_w n)$ | $O(n)$ | Word RAM bitwise parallel arithmetic across word size $w$, comparing multiple separator keys within a single register | Historical breakthrough beating the $O(\log n)$ comparison bound |
| X-fast Trie | Predecessor / Successor $O(\log \log U)$ | $O(n \log U)$ | Binary trie with hash tables at each depth level; binary searches for the deepest ancestor divergence | Theoretical framework underpinning the Y-fast Trie |
| Y-fast Trie | Insert / Delete / Search $O(\log \log U)$ | $O(n)$ Strictly Linear | Combines X-fast Trie with clustered balanced search trees to reduce storage to linear bounds | Optimal predecessor dictionary; theoretical IP routing tables |
| Hash Array Mapped Trie (HAMT) | Lookup / Insert / Update Amortized $O(1)$ ($\approx \log_{32} n$) | $O(n)$ with high sub-tree sharing | Trie combined with sparse bitmap indexing; zero memory overhead for null pointers | Default immutable Map/Set in Clojure, Scala, and Rust ecosystems |
| Wavelet Tree | Character Count & Rank/Select $O(\log \sigma)$ | Succinct $O(n \log \sigma)$ bits | Recursively partitions alphabet $\sigma$ into nested bit vectors, reducing arbitrary text queries to bit ranks | Full-text compressed indexing, bioinformatics genomics, FM-index |
| Soft Heap | Insert/Meld $O(1)$, DeleteMin $O(\log(1/\epsilon))$ | $O(n)$ | Sacrifices key exactness for at most $\epsilon \cdot n$ keys (corrupted keys) in exchange for constant-time melds | Key sub-routine in Chazelle's theoretically optimal Minimum Spanning Tree algorithm |
| BK-Tree (Burkhard-Keller) | Metric space range & nearest neighbor query | $O(n)$ | Exploits the metric Triangle Inequality $ | d(x, y) - d(x, z) |
| VP-Tree (Vantage-Point) | Metric nearest neighbor search in high dimensions | Build $O(n \log n)$, Query $O(\log n)$ | Recursively bisects metric spaces into spherical shells around chosen vantage points | High-dimensional similarity search, visual and audio feature recall |
| Merkle Tree | Inclusion proof verification $O(\log n)$ | $O(n)$ | Cryptographic hash tree where leaf nodes store data hashes and parents store the hash of concatenated children | Blockchain state proofs (Ethereum/Bitcoin), Git commit trees, BitTorrent |
| Gap Buffer | Cursor Insert / Delete $O(1)$ | $O(n)$ | Shifts an unallocated memory buffer gap directly to the cursor position; near-zero overhead for localized edits | The core text buffer backing GNU Emacs |
| Piece Table | Arbitrary Insert / Delete / Undo $O(1) \sim O(\log n)$ | $O(n)$ | Separates text into an immutable original buffer and an append-only add buffer, tracked via a piece descriptor list | Text buffer engine in VS Code; instantaneous unlimited Undo/Redo |
2. Competitive Programming Optimization Techniques
| Technique / Paradigm | Problem Domain | Target Optimization | Core Algorithmic Mechanics |
|---|---|---|---|
| Heavy-Light Decomposition (HLD) | Arbitrary path and subtree queries on trees | Transforms tree queries to array segments | Decomposes tree edges into heavy and light paths; maps heavy paths to continuous Segment Tree intervals in $O(\log^2 n)$ |
| Segment Tree Beats (Ji Driver) | Interval modulo and range capping ($\min=v$) | Solves interval min/max updates | Maintains maximum, strictly second-maximum, and maximum counts; prunes recursion when updates fall between 1st and 2nd maximums |
| Li Chao Segment Tree | Dynamic envelope of linear functions $y = kx + b$ | Point queries over line sets | Maintains the dominant segment over dyadic intervals in $O(\log n)$; accelerates dynamic programming convex hull tricks |
| Mo's Algorithm | Offline range queries on arrays | Amortizes unordered queries | Partitions array into $\sqrt{n}$ blocks; sorts queries by $(L / \sqrt{n}, R)$, bounding two-pointer movement to $O(n \sqrt{q})$ |
| WQS Binary Search (Aliens Trick) | Convex-constrained optimization ($\le K$ selections) | Eliminates count constraint $K$ | Injects Lagrange multiplier penalty $\lambda$ per item; binary-searches $\lambda$ to find the unconstrained optimal cost matching $K$ items |
| Slope Trick | Convex piecewise linear DP functions | Compresses function representations | Tracks only changing breakpoint coordinates using two priority queues (multisets), maintaining slope transitions in $O(\log n)$ |
| Centroid Decomposition | Tree path problems and distances | Divide-and-conquer on trees | Recursively locates the tree centroid (subtrees $\le n/2$) to build a balanced centroid tree of depth $O(\log n)$ |
3. Theoretical Complexity Lower Bounds & Conjectures
| Conjecture / Theorem | Theoretical Lower Bound | Target Problem Domain | Profound Theoretical Consequence |
|---|---|---|---|
| 3SUM Conjecture | $\Omega(n^2)$ Lower Bound | Finding three elements summing to zero ($a + b + c = 0$) | Strongly believed to lack an $O(n^{2-\epsilon})$ sub-quadratic solution; serves as the reduction anchor for computational geometry bounds |
| Strong Exponential Time Hypothesis (SETH) | $2^n$ Lower Bound | Deciding $k$-SAT problems | Cornerstone of fine-grained complexity: Proves that string Edit Distance strictly cannot be solved in strongly sub-quadratic $O(n^{2-\epsilon})$ time |
| All-Pairs Shortest Path (APSP) | $\Omega(n^3)$ Lower Bound | Dense directed weighted graph shortest paths | Believed to lack an $O(n^{3-\epsilon})$ truly sub-cubic algorithm |
| Matrix Multiplication Exponent ($\omega$) | $\Omega(n^2) \le O(n^\omega)$ ($\omega \approx 2.371$) | Multiplying two $n \times n$ matrices | Naive $O(n^3)$ was broken by Strassen ($n^{2.807}$); modern theoretical limit approaches 2.371; ongoing open question if $\omega = 2$ |
| Dynamic Graph Connectivity | $\Omega(\log n)$ per update/query | Cell-Probe Model | Proves that maintaining dynamic edge insertions/deletions and connectivity queries cannot achieve mutual $O(1)$ |
4. Sorting Networks & Hardware Parallel Algorithms
In GPU CUDA pipelines, FPGA circuits, and SIMD vector registers, branchless, fixed-step sorting networks provide optimal hardware throughput:
| Network / Algorithm | Comparator Depth (Clock Cycles) | Total Comparators (Circuit Area) | Core Mechanics & Application |
|---|---|---|---|
| Bitonic Sorting Network | $O(\log^2 n)$ | $O(n \log^2 n)$ | Recursively builds bitonic sequences (first half ascending, second half descending) before parallel merging; standard GPU CUDA parallel sort |
| Odd-Even Merge Network | $O(\log^2 n)$ | $O(n \log^2 n)$ | Batcher network merging odd-indexed and even-indexed elements independently before running crossover cleanup comparators |
| Zero-One Principle | - | - | Fundamental Theorem: If a deterministic comparison network correctly sorts all $2^n$ binary inputs of 0s and 1s, it is guaranteed to sort arbitrary real numbers |
| Shear Sort | $O(\sqrt{n} \log n)$ | Designed for 2D mesh arrays | Alternates snake-like row sorts with unidirectional column sorts until the 2D grid settles into total order |
| AKS Sorting Network | Theoretical depth $O(\log n)$ | $O(n \log n)$ | Strictly achieves the theoretical $O(\log n)$ depth bound using expander graphs, but astronomical constant factors prevent physical circuit realization |
5. Esoteric & Geek Humorous Sorting Algorithms
Serving as classic illustrations of probability, computational complexity, and developer folklore, these algorithms highlight absurd yet mathematically rigorous extremes:
| Algorithm | Average Time Complexity | Worst Time Complexity | Space Complexity | The Absurd Mechanics |
|---|---|---|---|---|
| Bogo Sort | $O(n \cdot n!)$ | Unbounded ($\infty$) | $O(1)$ | Checks if array is sorted; if not, shuffles elements completely at random until it accidentally settles in order (Infinite Monkey Theorem) |
| Slow Sort | $O(n^{\frac{\log n}{2+\epsilon}})$ | Extremely slow | $O(n)$ | Implements "Multiply and Surrender": recursively sorts first and second halves, moves the maximum to the end, then sluggishly sorts the first $n-1$ elements |
| Stooge Sort | $O(n^{\log_3 4}) \approx O(n^{2.71})$ | $O(n^{2.71})$ | $O(1)$ | Compares ends, then recursively sorts the first 2/3, the last 2/3, and the first 2/3 again |
| Sleep Sort | $O(n + \max(A))$ | Bounded by timer jitter | $O(n)$ threads | 4chan folklore: Spawns an asynchronous thread for each element $x$ executing sleep(x), outputting $x$ upon wakeup (maps value magnitude to elapsed time) |
| Spaghetti Sort | Physical $O(n)$ | Physical $O(n)$ | $O(n)$ | Analog computer: Cut dry spaghetti noodles to match each value's length, tap them vertically against a table, and lower your hand from above; first noodle touched is the maximum |
| Stalin Sort | Strictly Linear $O(n)$ | $O(n)$ | $O(1)$ | An autocratic single pass: Any element that violates monotonic non-decreasing order is immediately purged and dropped from existence; the remainder is guaranteed sorted |
| Miracle Sort | Wait for Cosmic Event ($\infty$) | $\infty$ | $O(1)$ | Leaves the array in memory in an infinite loop without modifications, praying that cosmic ray radiation induces hardware bit-flips to make the array sorted |
| Quantum Bogo Sort | Multiverse $O(n)$ | $O(n)$ | $O(1)$ | Under the Many-Worlds interpretation: shuffles with a quantum random source; if the array is unsorted in this universe, instantly destroy the universe; the surviving universe is sorted |