Lesson 064
Space Complexity
Memory, the call stack & the time–space tradeoff
1:00How to measure and reason about the memory an algorithm uses, from the call stack to the time–space tradeoff.
By the end, you can
- Distinguish total space from auxiliary space and explain which one we report.
- Identify what counts as auxiliary space (temporaries, data structures, call-stack frames).
- Compute the call-stack depth of a recursive algorithm and express it in Big O.
- Compare the space complexity of recursive factorial (O(n)) with iterative factorial (O(1)).
- Classify a given algorithm into O(1), O(log n), O(n), or O(n²) auxiliary space.
- Explain why O(1) does not mean zero memory.
- Describe the time–space tradeoff and give memoized Fibonacci as an example.
- Apply worst-case reasoning when assigning a space complexity class.
Up next in Recursion, Paradigms & Algorithm Analysis
