Card 04/ 08
Space Complexity and the Call Stack
Extra space counts the memory a function adds, including one frame for every call still waiting.
Space complexity is how the extra memory a function needs grows with its input, not counting the memory the input already takes. Recursion adds memory the code does not show: every call that has not yet returned keeps a frame, the memory holding its arguments, its local variables and the point to resume from. This card covers how to count that memory, using a recursive sum.
The function below creates no list or dictionary, so it looks as if it needs no extra memory. On 500 items it returns 125,250. On 5,000 it fails:
def sum_from(items: list[int], index: int) -> int:
if index == len(items):
return 0
return items[index] + sum_from(items, index + 1)sum_from([1, 2, 3, 4], 0) = 10
recursion limit: 1000
500 items: 125250
5000 items: RecursionErrorBefore the steps: called on a list of four items, how many frames are on the stack at the deepest point?
Five: one for each index from 0 to 4. The call at index 4, the base case, finds no items left and returns without calling again.
The steps follow the stack through that call, one line per frame, the newest on top.
The call stack for sum_from([1, 2, 3, 4], 0), top frame first, printed by a traced run
First call
One frame, waiting to add 1 to whatever the next call returns.
sum_from(items, 0) waiting: 1 + ?Third call
Three frames, each holding one item and waiting.
sum_from(items, 2) waiting: 3 + ?
sum_from(items, 1) waiting: 2 + ?
sum_from(items, 0) waiting: 1 + ?Base case
Five frames for four items: the deepest point.
sum_from(items, 4)
sum_from(items, 3) waiting: 4 + ?
sum_from(items, 2) waiting: 3 + ?
sum_from(items, 1) waiting: 2 + ?
sum_from(items, 0) waiting: 1 + ?Unwinding
Index 2 has returned 7, and its frame is gone.
sum_from(items, 1) waiting: 2 + ?
sum_from(items, 0) waiting: 1 + ?No frame can finish its addition until the call above it returns, so at the deepest point the stack holds n + 1 frames: O(n) extra space. This Python reported a recursion limit of 1,000 frames, which is why 5,000 items failed.
A traced run compared three versions at n = 900. The third passes items[1:], a copy of the list without its first item, instead of an index.
| Version | Time | Extra space | Stack depth | Items held in copies |
|---|---|---|---|---|
| A loop | O(n) | O(1) | 1 | 0 |
| Recursion with an index | O(n) | O(n) | 901 | 0 |
| Recursion with a slice | O(n²) | O(n²) | 901 | 404,550 |
So extra space counts every allocation that grows with n, and one frame for every call still waiting. The slice version holds a copy in every frame, 899 + 898 + … + 0 items in all, which is why it is O(n²).
The loop's total is not O(n): each pass overwrites the same variable. Nor is the input list, which existed before the call.
When two designs take the same time, extra space decides between them, and the depth of recursion decides whether a function runs on a large input at all.
← → move through sections and cards