Why Practice Complexity Analysis?
You cannot optimize what you cannot measure. In FAANG interviews, you must analyze every solution you propose before you even start coding.
Hand-Picked Problems
| Problem | Goal | Complexity |
|---|---|---|
| Two Sum | Compare $O(n^2)$ vs $O(n)$ | $O(n)$ Time, $O(n)$ Space |
| Binary Search | Analyze logarithmic growth | $O(\log n)$ Time |
| Fibonacci Number | Analyze recursion depth | $O(2^n)$ vs $O(n)$ |
| Merge Sort | Understand Divide & Conquer | $O(n \log n)$ Time |
| Rotate Image | Analyze matrix traversals | $O(n^2)$ Time |
| Permutations | Analyze factorial growth | $O(n!)$ Time |
| Word Search | Analyze grid backtracking | $O(n \times 3^L)$ |
| LRU Cache | Analyze amortized $O(1)$ | $O(1)$ Time |
Analysis Checklist
For every solution, ask:
- How many loops? (Nested = $O(n^2)$).
- Is the search space halved? (Halved = $O(\log n)$).
- Is there a recursion stack? (Depth = Space complexity).
- Are we using extra data structures? (HashMap/Array = $O(n)$ Space).