EasyComplexity Analysis
Big O
Big O describes how runtime or memory grows as input size increases. It lets you compare solutions without relying on machine-specific timing.
Intuition
Ask what work repeats as n grows. One pass is usually O(n), nested pair checks are often O(n^2), and halving search space is O(log n).
Complexity Analysis
Common classes: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n). Space complexity counts extra structures and recursion stack.
Common Mistakes
- Jumping to code before naming the invariant or state being maintained
- Forgetting edge cases such as empty input, one element, duplicates, and negative values
- Using a brute-force approach without explaining how the pattern improves it
Interview Notes
- State the brute force first, then explain the bottleneck and the optimization
- Say the time and space complexity before the interviewer asks
- Walk through one small example and one edge case
Best Practices
- Keep variable names tied to the invariant: left, right, seen, window, slow, fast
- Prefer simple control flow over clever one-liners in interviews
- Write tests for boundary cases after the main solution
Example Problems
- Contains Duplicate
- Binary Search
- Merge Sort