foundations
16 min
complexity
tradeoffs

Complexity Fluency

Big-O you can say out loud: time, space, and when it matters.

Covers: complexity · tradeoffs

Say it before they ask

After every approach: time and space in terms of n (and m if needed).

Patterns to memorize | Structure | Typical | |-----------|---------| | Hash map / set | O(1) avg lookup; O(n) space | | Sort then scan | O(n log n) | | Two pointers on sorted | O(n) | | Binary search | O(log n) | | BFS/DFS graph | O(V+E) | | Heap of size k | O(n log k) | | DP over n states | often O(n) or O(n·W) |

Space tradeoffs Interviewers love “I can trade O(n) space for O(n) time.” Offer the tradeoff even if you pick one.

Trap Claiming O(1) space while building a recursion stack of depth n — call it O(n) stack.

Crucible — Interview prep with real proof