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…
Practice — write it yourself
Space-for-time trade: first_duplicate(arr) returns the first value seen twice (or None). Use a set — O(n) extra space buys O(n) time.
Python 3 · runs in your browser · your draft is saved locally
📝 My notessaved in this browser