Space Complexity
Space complexity measures how an algorithm's memory usage grows, including the stack space used by recursive calls.
ONE FRAME PER LEVEL
PEAK 1
ALIVE AT ONCE
1
factorial(5) defers to factorial(4). Its frame stays alive while it waits: 1 in memory.
Next
factorial(4) defers to factorial(3). Its frame stays alive while it waits: 2 in memory.
Version
N
Intuition
Just like time complexity measures operations, space complexity measures the extra memory an algorithm needs as the input grows.
Concept
- Auxiliary Space: Extra space used (e.g., temp arrays, recursion stack).
- Input Space: Space to store the input itself (usually ignored in analysis).
- O(1) Space: Uses fixed memory regardless of N (e.g., iterative loops).
- O(N) Space: Memory grows linearly (e.g., recursion depth of N).
How it Works
Recursion Stack:
Every time a function calls itself, the computer must "remember" where to return to. This info is stored in a "Stack Frame". If you call a function N times recursively, you use O(N) stack space.
Step-by-Step Breakdown
Watch the visualization:
- Each
factorial(n)call adds a block to the stack. - The stack grows until the base case is reached.
- Then, frames are popped off as functions return.
Trace: factorial(4) on the call stack
call f(4)
A frame holding n = 4 and a return address goes on the stack. The multiply cannot run yet, because it needs an answer from f(3), so the frame has to stay.
depth 1
call f(3)
Same again, and f(4) is still waiting underneath.
depth 2
call f(2)
Three frames now alive at once, none of them finished.
depth 3
call f(1)
The base case. It returns 1 without calling anything, so this is as deep as the stack goes.
depth 4
return 1
That frame pops, and f(2) can finally do its multiply.
depth 3
return 2
2 * 1. The frame pops and unblocks f(3).
depth 2
return 6
3 * 2, and f(4) is unblocked.
depth 1
return 24
4 * 6. The last frame pops and the stack is empty again.
depth 0
peak
Four frames held simultaneously for n = 4, so the peak grows one-for-one with the input. Writing the same computation as a loop holds one accumulator instead, which is the O(1) alternative — and the reason a deep recursion overflows where a loop does not.
O(N)
When to Use
- When optimizing for devices with limited RAM (embedded systems, mobile).
- To avoid "Stack Overflow" errors in deep recursion.
When NOT to Use
- When you have plenty of memory and recursion makes code cleaner.
How to Identify
"Memory Limit Exceeded", "In-place algorithm required", "O(1) extra space".
Applying for software engineering roles? Free, no sign-up: