Time vs Space Trade-off
Most optimizations trade memory for speed or vice versa — using more space (e.g., a cache or auxiliary array) often reduces time complexity.
Time vs Space is like packing for a trip: bring a GPS (extra luggage = space) and you save hours of asking for directions (time). Carry nothing and you'll wander forever.
Classic examples: prefix sum arrays trade O(n) space for O(1) range queries instead of O(n) per query. Memoization trades O(n) space for exponentially less time. In-place algorithms use O(1) extra space but may be slower or harder to implement correctly. Hash maps trade O(n) space for O(1) average lookup instead of O(n) linear scan.
Space complexity includes the call stack for recursive algorithms — a naive recursive fibonacci uses O(n) stack space even though you might not think of it as 'storing' anything. Iterative solutions avoid this. Cache-conscious algorithms prefer sequential memory access (arrays) over pointer-chasing (linked lists) because CPU cache lines load 64 bytes at a time — a linked list traversal generates O(n) cache misses; an array traversal generates O(n/8) on 64-bit systems. This is why practical performance sometimes inverts theoretical Big O comparisons.
I always state both time and space complexity. When proposing an optimization, I explicitly call out the trade-off: 'I can reduce this from O(n²) time to O(n) by using an O(n) hash map.' Interviewers appreciate knowing you understand the cost. I also mention auxiliary space vs total space — in-place algorithms use O(1) auxiliary space but the input itself might be O(n).
Recursive solutions are NOT free on space. A recursive DFS on a skewed binary tree uses O(n) stack space, which can cause a stack overflow for large inputs. Always mention this and offer to convert to iterative with an explicit stack.