High-yield mental model digests, asymptotic recurrence master relations, and space-repetition drills. Master the 14 core patterns and invariant proofs 60 minutes before your FAANG round.
Let c = log_b(a) (critical exponent). Compare f(N) with N^c.
| Case | Condition | Asymptotic Bound Θ(N) | Classic Example | Intuition |
|---|---|---|---|---|
| Case 1: Leaves Dominate | f(N) = O(N^(c - ε)) | Θ(N^(log_b a)) | Strassen Matrix Mult: T(N) = 7T(N/2) + O(N^2) | Leaf level has more work than all internal levels combined. |
| Case 2: Even Distribution | f(N) = Θ(N^c log^k N) | Θ(N^c log^(k+1) N) | Merge Sort: T(N) = 2T(N/2) + O(N) | Every level of the recursion tree performs equal work: log(N) levels * N. |
| Case 3: Root Dominates | f(N) = Ω(N^(c + ε)) | Θ(f(N)) | Binary Search Variant: T(N) = T(N/2) + O(N) | Top level dominates; geometric decay makes subproblems negligible. |
| Akra-Bazzi Generalization | T(x) = g(x) + Σ a_i T(b_i x + h_i(x)) | Θ(x^p (1 + ∫ g(u)/u^(p+1) du)) | Unequal Partition: T(N) = T(N/3) + T(2N/3) + O(N) | Handles arbitrary non-uniform divide-and-conquer partitions. |
| Data Structure | Access (Average) | Search (Worst) | Insertion (Worst) | Deletion (Worst) | Space Bounds | FAANG Invariant Note |
|---|---|---|---|---|---|---|
| Hash Table (Separate Chaining) | O(1) | O(N) | O(1) amortized | O(1) amortized | O(N) | Load factor α < 0.75 avoids clustering degradation. |
| Red-Black Tree (Self-Balancing) | O(log N) | O(log N) | O(log N) | O(log N) | O(N) | Height strictly bounded by 2 log_2(N + 1). |
| Disjoint Set Union (DSU) | O(α(N)) | O(α(N)) | O(α(N)) | O(α(N)) | O(N) | Union by Rank + Path Compression yields inverse Ackermann α(N) < 5. |
| Binary Min/Max Heap | O(1) peek | O(N) search | O(log N) | O(log N) extract | O(N) | Complete binary tree in contiguous array: parent=(i-1)/2. |
| Trie (Prefix Tree) | O(L) | O(L) | O(L) | O(L) | O(ALPHABET * N * L) | Search complexity bounded by string length L, independent of N keys! |
Bilateral Monotonicity: The array must be monotonic (sorted or strictly non-decreasing). When moving pointer L to the right strictly increases sum, and moving pointer R to the left strictly decreases sum, candidate pairs outside the bounding window can be pruned in O(1) without evaluation.