Lesson 0.1 had a pattern: the fast duplicate check was fast because it remembered what it had seen. Most optimisations in this roadmap work that way. They trade memory for time. So the real skill isn't "use less memory", it's deciding what is worth remembering, and knowing what that costs, especially in Python where every stored value is bigger than it looks.
The running example is Fibonacci, solved four ways, from exponential time to logarithmic time, purely by changing what we remember. Then we cover what space complexity counts, real Python memory costs, in-place algorithms, streaming, and recursion depth.
1. What space complexity counts
Auxiliary space is the extra memory an algorithm uses beyond its input. That's usually what interviewers mean.
| Counts | Usually not counted (say so) |
|---|---|
| Extra lists, sets, dicts you create | The input itself |
Copies (sorted(a), slices, list(a)) |
The output you must return |
| The recursion call stack | |
| Temporary buffers inside library calls you rely on |
Two habits:
- Say which you mean: "O(n) auxiliary space for the set; the output is O(1)."
- Don't forget the stack: a recursive function of depth d uses O(d) space even if it creates no data structures.
2. A full walkthrough: Fibonacci, by deciding what to remember
Problem. Return F(n), where F(0) = 0, F(1) = 1 and F(n) = F(n−1) + F(n−2).
ML context. The same structure (a value defined by smaller values of itself) is the heart of dynamic programming: edit distance between strings, Viterbi decoding over label sequences, sequence alignment. Module 12 builds on exactly this progression.
Step 1: Clarify
How large can n be? Do we need the exact integer (Python integers grow without limit) or a value modulo some number? Assume exact, with n up to 10⁶ for now.
Step 2: Brute force: the definition, as code
calls = 0
def fib_naive(n):
global calls
calls += 1
if n < 2:
return n
return fib_naive(n - 1) + fib_naive(n - 2)
assert [fib_naive(i) for i in range(10)] == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
calls = 0
fib_naive(25)
print(f"fib(25) made {calls:,} calls")
assert calls > 200_000
It's correct, but 242,785 calls for n = 25. Why?
Each call makes two more, so the call tree roughly doubles per level: O(φⁿ) ≈ O(1.618ⁿ) time, exponential. The space is O(n): only one root-to-leaf path of calls is on the stack at a time.
Against the constraints: n = 50 would need about 4 × 10¹⁰ calls. Hopeless, so we optimise.
Step 3: Optimise: what work is repeated? Remember it (memoisation)
The tree computes the same subproblems over and over. First principle: if you'll need an answer again, store it.
def fib_memo(n, memo=None):
if memo is None:
memo = {0: 0, 1: 1}
if n not in memo:
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
assert [fib_memo(i) for i in range(10)] == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
assert fib_memo(90) == 2880067194370816120
print("memoised version works")
- Time: each F(k) is computed once: O(n).
- Space: O(n) for the memo, plus O(n) stack depth.
- New problem under a new constraint: n = 10⁶ would recurse a million levels deep; Python's default recursion limit is about 1,000. The constraint on n now breaks the recursive shape (section 6).
Optimisation 2: what do we actually need to remember?
Computing F(k) needs only F(k−1) and F(k−2). Everything older can be forgotten. So keep two numbers, not a table.
def fib_iter(n):
prev, cur = 0, 1 # F(0), F(1)
for _ in range(n):
prev, cur = cur, prev + cur # slide the window forward by one
return prev
assert [fib_iter(i) for i in range(10)] == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
assert fib_iter(90) == 2880067194370816120
print(f"fib(100,000) has {len(str(fib_iter(100_000))):,} digits")
- Time: O(n) additions. Space: O(1) numbers (each number has O(n) digits, so be precise if asked: the count of stored values is constant).
- Why this works: we noticed the dependency window has width 2. That observation, "how far back does each step look?", turns many O(n)-space dynamic programs into O(1)-space ones.
Optimisation 3: when n is astronomically large
What if n = 10¹⁸ (with the answer taken modulo 10⁹ + 7)? Even O(n) is impossible: that's 10¹⁸ steps. The constraint forces O(log n). The fast doubling identities let us jump from F(k) to F(2k):
- F(2k) = F(k) · (2·F(k+1) − F(k))
- F(2k+1) = F(k)² + F(k+1)²
Halving n each step gives O(log n) steps (lesson 0.2).
MOD = 10**9 + 7
def fib_fast(n, mod=MOD):
"""Returns (F(n), F(n+1)) modulo mod, in O(log n) steps."""
if n == 0:
return 0, 1
a, b = fib_fast(n // 2, mod) # a = F(k), b = F(k+1), with k = n // 2
c = a * ((2 * b - a) % mod) % mod # F(2k)
d = (a * a + b * b) % mod # F(2k + 1)
return (d, (c + d) % mod) if n % 2 else (c, d)
def fib_iter_mod(n, mod=MOD):
prev, cur = 0, 1
for _ in range(n):
prev, cur = cur, (prev + cur) % mod
return prev
for n in range(0, 2000, 37):
assert fib_fast(n)[0] == fib_iter_mod(n)
print("fib(10**18) mod 1e9+7 =", fib_fast(10**18)[0])
Recursion depth here is only about log₂ n ≈ 60, so the stack is no longer a problem.
The whole progression
| Constraint | Approach | Time | Space | What we chose to remember |
|---|---|---|---|---|
| n ≤ 25 | Naive recursion | O(1.618ⁿ) | O(n) stack | Nothing |
| n ≤ 10³ | Memoisation | O(n) | O(n) memo + stack | Every answer |
| n ≤ 10⁶ | Two variables | O(n) | O(1) values | Only the last two |
| n ≤ 10¹⁸, modulo m | Fast doubling | O(log n) | O(log n) stack | A pair, via halving |
Quick check
Why does the two-variable Fibonacci use O(1) space while memoisation uses O(n)?
Show the answer
B. Each step only depends on the previous two values, so older answers can be forgotten instead of stored — Space depends on how far back each step looks. A dependency window of width 2 needs only two stored values.
3. What memory really costs in Python
Big-O hides constants, but in Python the constants for memory are large enough to change decisions.
| Storage | Approx. bytes per value (CPython, 64-bit) |
|---|---|
list of ints |
8 (pointer) + 28 (int object) ≈ 36 |
set or dict of ints |
roughly 50 to 100, depending on fill |
array('q'), NumPy int64 |
8 |
NumPy int8, bytearray |
1 |
| Bit set (one bit per possible value) | ⅛ |
import sys
from array import array
values = list(range(10**6, 10**6 + 50_000)) # ints above the small-int cache
list_bytes = sys.getsizeof(values) + sum(sys.getsizeof(v) for v in values)
set_obj = set(values)
set_bytes = sys.getsizeof(set_obj) + sum(sys.getsizeof(v) for v in values)
array_bytes = sys.getsizeof(array("q", values))
for name, b in [("list", list_bytes), ("set", set_bytes), ("array('q')", array_bytes)]:
print(f"{name:>11}: {b / len(values):6.1f} bytes per value")
assert array_bytes < list_bytes < set_bytes
Why this matters for ML work: a feature column of 10⁸ floats is 800 MB as a NumPy array and several GB as a Python list. Choosing the representation is part of the algorithm.
4. In place: use the input as your workspace
When memory is tight and you may modify the input, work inside it.
Problem. Reverse a list.
Brute force: build a reversed copy: a[::-1]. O(n) time, O(n) extra space.
First principle: element i belongs at position n − 1 − i. Swap the two ends, move inward, stop in the middle.
def reverse_in_place(a):
left, right = 0, len(a) - 1
while left < right:
a[left], a[right] = a[right], a[left] # swap the ends
left += 1
right -= 1
for data in ([], [1], [1, 2], ["a", "b", "c", "d", "e"], list(range(10))):
expected = data[::-1]
reverse_in_place(data)
assert data == expected
print("in-place reverse works")
O(n) time, O(1) extra. Two pointers moving inward is the core of module 03.
5. Streaming: never hold what you don't need
If you only need an aggregate (a sum, a count, a maximum), you don't need all values at once. A generator produces values one at a time.
import tracemalloc
def peak_kib(fn):
tracemalloc.start()
fn()
_, peak = tracemalloc.get_traced_memory()
tracemalloc.stop()
return peak / 1024
n = 1_000_000
list_peak = peak_kib(lambda: sum([x * x for x in range(n)])) # builds a full list first
gen_peak = peak_kib(lambda: sum(x * x for x in range(n))) # one value at a time
print(f"list: {list_peak:,.0f} KiB peak, generator: {gen_peak:,.1f} KiB peak")
assert gen_peak < list_peak / 100
Same answer, same O(n) time, but O(1) instead of O(n) memory. For ML pipelines that read files of billions of rows, this is the difference between running and crashing.
6. Recursion depth is memory too
Each recursive call keeps a stack frame. Python limits depth to about 1,000 by default, so a recursion that's "only" O(n) deep fails long before memory runs out.
import sys
def total_recursive(a, i=0):
return 0 if i == len(a) else a[i] + total_recursive(a, i + 1)
def total_iterative(a):
s = 0
for x in a:
s += x
return s
data = list(range(5_000))
try:
total_recursive(data)
print("recursion succeeded")
except RecursionError:
print(f"RecursionError at depth > {sys.getrecursionlimit()}: switch to a loop")
assert total_iterative(data) == sum(data)
In interviews: recursion is fine when depth is O(log n) (binary search, balanced trees, fast doubling). When depth can reach n (linked lists, skewed trees, naive DFS on long paths), convert to a loop with an explicit stack, or say you would.
7. When memory is the binding constraint
Problem. A log contains 10⁸ user IDs, each between 0 and 10⁸ − 1. Count how many distinct IDs appear. Memory limit: 64 MB.
Brute force with a set: len(set(ids)). Correct, O(n) time, but each stored int costs 50 to 100 bytes:
several GB. Ruled out by the memory constraint, not by time.
First principle: we only need one yes/no per possible ID. The IDs are small, dense integers, so index by value (the same idea as counting in lesson 0.3) and store one bit per ID: 10⁸ bits = 12.5 MB.
def count_distinct_bitset(ids, max_id):
bits = bytearray((max_id + 8) // 8) # one bit per possible ID
distinct = 0
for x in ids:
byte, mask = x >> 3, 1 << (x & 7) # which byte, which bit inside it
if not bits[byte] & mask:
bits[byte] |= mask
distinct += 1
return distinct
import random
rng = random.Random(5)
ids = [rng.randrange(0, 100_000) for _ in range(200_000)]
assert count_distinct_bitset(ids, 99_999) == len(set(ids))
print(f"bitset for 10^8 IDs would need {(10**8 + 7) // 8 / 1e6:.1f} MB")
| If the constraint becomes… | Approach | Memory |
|---|---|---|
| IDs are arbitrary strings, memory fine | Python set | O(distinct), GBs at 10⁸ |
| IDs dense in 0..N | Bit set | N/8 bytes |
| IDs arbitrary, memory tiny, ≈ answer OK | HyperLogLog sketch | kilobytes, ~1% error |
| IDs arbitrary, exact answer, disk available | External sort, then count runs | small RAM, disk passes |
Quick check
IDs are random 64-bit integers (not dense), there are 10⁸ of them, and you have 64 MB. Why does the bit set no longer work, and what are the options?
Show the answer
C. A bit set needs one bit per possible value: 2⁶⁴ bits is impossible; use an approximate sketch like HyperLogLog, or an exact external sort on disk — Indexing by value only works when the value range is small. Sparse huge ranges need hashing, sketches or disk.
8. Saying it out loud
"Naive recursion is O(1.6ⁿ) time because it recomputes the same subproblems; O(n) stack. Memoising stores each answer once: O(n) time and space, but the recursion depth breaks Python's limit around n = 1,000. Each step only needs the previous two values, so I'll keep two variables: O(n) time, O(1) space. If n were 10¹⁸ I'd use fast doubling for O(log n)."
Quick check
A recursive DFS on a graph shaped like a long chain of 10⁵ nodes crashes in Python. The algorithm is O(n) time. What's wrong, and what fixes it?
Show the answer
A. Recursion depth reaches 10⁵, beyond Python's default limit of about 1,000; rewrite it with an explicit stack (or raise the limit carefully) — Stack depth is memory with a hard ceiling in Python. Deep recursion should become iteration.
Check yourself
- What does auxiliary space include and exclude?
- Walk Fibonacci from naive recursion to fast doubling, giving time and space for each.
- Why does the two-variable version need only O(1) values?
- Roughly how many bytes does one int cost in a Python list, a set, and a NumPy
int64array? - When is a generator better than a list, and what does it save?
- When does a bit set beat a hash set, and when is it impossible?
Answers
- Extra structures, copies and the recursion stack; usually excludes the input and the required output (say so).
- Naive: O(1.618ⁿ) time, O(n) stack. Memo: O(n) time and space. Two variables: O(n) time, O(1) values. Fast doubling: O(log n) time, O(log n) stack.
- Each step depends only on the previous two values, so older ones can be discarded.
- About 36 bytes, about 50 to 100 bytes, 8 bytes.
- When you only need an aggregate or a single pass: it keeps O(1) values in memory instead of O(n).
- When values are small dense integers (index by value, one bit each); impossible when the value range is huge and sparse.