Stage 1 · Code
Mock Interviews & Strategy
Complexity Analysis
Time and space complexity isn't just trivia — it's the language you use to compare approaches and convince interviewers your solution is optimal.
Big-O Refresher
Big-O describes the upper bound of how runtime or memory grows as input size increases. It drops constants and lower-order terms because we care about scaling behavior, not micro-optimizations.
Key rules of thumb:
- Loops: k nested loops over n → O(nᵏ). Two separate loops over n → O(n) (they're added, not multiplied).
- Recursion: divide in half each call → O(log n) depth, O(n log n) total if O(n) work per level.
- Recursion (branching): binary branching to depth n → O(2ⁿ). Memoization prunes this to O(n²) or O(n).
- Sorting: assumed O(n log n). If you sort, that's likely the bottleneck.
- Hash maps: O(1) average case, O(n) worst case (hash collisions). But treat as O(1) in interviews.
Some operations are O(1) on average even though individual calls may be O(n). Classic example: dynamic array (Go slice) append. Most appends are O(1), but when the array needs to resize, that single append is O(n). Spread across n appends, the average is O(1). Mention amortized analysis when discussing dynamic arrays or hash map resizing.
Common Complexity Patterns
Learn to recognize these patterns instantly:
- Two-pointer → O(n) time, O(1) space. Only works on sorted arrays or linked lists.
- Sliding window → O(n) time, O(k) space where k = window size. One pass, expand and contract.
- DFS/BFS on graph → O(V + E) time, O(V) space for visited set + recursion/queue.
- Binary search → O(log n) time, O(1) space (iterative).
- Dynamic programming → O(n²) or O(m·n) time, O(n) to O(n²) space depending on optimization.
- Backtracking → O(2ⁿ) or O(n!) worst case. Pruning matters but doesn't change worst-case bound.
- Heap operations → O(log k) per push/pop. Building from array: O(k).
How to Analyze During an Interview
Follow this script after writing your solution:
- Time: 'Let's analyze the time complexity. The outer loop runs n times. Inside, we do a hash map lookup which is O(1), so total O(n). The sorting step before this would be O(n log n), making the bottleneck the sort.'
- Space: 'For space, we store at most n elements in the hash map, so O(n). If we sorted in place, space would be O(1) besides the input.'
- Justify: 'Could we do better? Sorting is O(n log n), but we know comparison sort is Ω(n log n). So this is optimal for a comparison-based approach.'
- Edge cases: 'If the input is already sorted, we could use two pointers for O(n) time and O(1) space. But since the problem doesn't guarantee sorted input, our current solution is correct for all cases.'
Complexity analysis should take 30-60 seconds. Don't narrate every line. Group operations: 'The recursive function visits each node once, so O(n). The path copy on each leaf is O(n) per leaf, so worst-case O(n²).' If there's a tricky part, focus on that.
Practice Problems
Key Points
- Know the 6 common complexities by heart and recognize which pattern maps to which.
- For loops: count nesting depth. For recursion: depth × branching factor.
- Mention amortized analysis for hash maps and dynamic arrays — it shows depth of understanding.
- State complexity after coding, not before. Let the code speak first.
- Justify optimality: 'Is there an Omega(n) lower bound? Can we prove we can't do better?'
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.