Counter space, not cooking time
Space Complexity
The analogy
Some recipes need every bowl in the kitchen; others use one pan. Space complexity asks how much extra room the work needs as the data grows — and sometimes you happily spend memory to save time, or the reverse.
Visualizer
Counter space, not time
step 1 / 6| aux memory | grows with n? | why | |
|---|---|---|---|
| bubbleSort | |||
| quickSort | |||
| mergeSort | |||
| countingSort |
Time is not the only budget. Space complexity counts the EXTRA memory an algorithm needs, ignoring the input itself.
# auxiliary space, excluding the input bubble_sort(a) # O(1) swaps in place quick_sort(a) # O(log n) call stack merge_sort(a) # O(n) scratch lists sum(x for x in a) # O(1) generator sum([x for x in a]) # O(n) builds a list
Check yourself
"In place" means auxiliary space of…