Review & Cheat Sheet
[!NOTE] This module explores the core principles of Review & Cheat Sheet, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.
1. Key Takeaways
- Recursion: Solving a problem by solving smaller instances of the same problem. Requires a Base Case to stop.
- Divide & Conquer: Divide (split), Conquer (recurse), Combine (merge). Example: Merge Sort.
- Backtracking: Depth-First Search on a state space tree. If a path fails, undo (backtrack) and try another. Example: N-Queens.
- Master Theorem: Shortcut for
T(n) = aT(n/b) + f(n). Compares root workf(n)vs leaf workn<sup>log<sub>b</sub></sup>(a). - Recursion Tree: Visual method to sum work per level when Master Theorem fails.
2. Interactive Flashcards
Test your knowledge! Click to flip.
What is the Base Case?
The condition that stops the recursion preventing infinite loops (Stack Overflow).
1 / 5
3. Cheat Sheet: Common Recurrences
| Algorithm | Recurrence | Master Theorem Case | Complexity |
|---|---|---|---|
| Binary Search | T(n) = T(n/2) + O(1) |
Case 2 (Balanced) | O(log n) |
| Merge Sort | T(n) = 2T(n/2) + O(n) |
Case 2 (Balanced) | O(n log n) |
| Quick Sort (Best) | T(n) = 2T(n/2) + O(n) |
Case 2 (Balanced) | O(n log n) |
| Karatsuba Mult | T(n) = 3T(n/2) + O(n) |
Case 1 (Leaf Heavy) | O(n<sup>1</sup>.58) |
| Strassen Matrix | T(n) = 7T(n/2) + O(n<sup>2</sup>) |
Case 1 (Leaf Heavy) | O(n<sup>2</sup>.81) |
| Selection Algorithm | T(n) = T(n/5) + T(7n/10) + n |
Tree Method | O(n) |
4. Next Steps
Recursion is the foundation. The next logical step is to optimize recursion using Memoization.
Go to Module 12: Dynamic Programming →
5. Practice in the Vault
Looking to solidify your understanding? Head over to the Problem Vault to solve curated problems related to this module with detailed walkthroughs and optimal solutions.