VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 00: The method and Big-O

Lesson 0.4 of 6 in this moduleFree

Space complexity: what you choose to remember

Memory as a design choice: auxiliary space, recursion stacks, what Python values really cost, in-place and streaming techniques, and Fibonacci taken from exponential time to O(log n) by deciding what to remember.

about 15 min 9 Python examples 3 quick checks

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

python
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?

the recursion tree for fib(5); fib(3) is computed twice and fib(2) three times, the same subproblems again and again.
Diagram— the recursion tree for fib(5); fib(3) is computed twice and fib(2) three times, the same subproblems again and again.

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.

python
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.

python
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).

python
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)?

  1. It uses a faster language feature
  2. Each step only depends on the previous two values, so older answers can be forgotten instead of stored
  3. Memoisation is wrong
  4. Python optimises it automatically
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.

approximate bytes per stored integer: about 36 in a Python list of ints, 8 in a typed 64-bit array, 1 in an 8-bit NumPy array, one eighth of a byte in a bit set.
Chart— approximate bytes per stored integer: about 36 in a Python list of ints, 8 in a typed 64-bit array, 1 in an 8-bit NumPy array, one eighth of a byte in a bit set.
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) ⅛
python
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.

three frames reversing [a, b, c, d, e] in place: swap a and e, swap b and d, the pointers meet at c and stop.
Diagram— three frames reversing [a, b, c, d, e] in place: swap a and e, swap b and d, the pointers meet at c and stop.
python
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.

python
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.

python
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.

memory to record which of 100 million possible IDs appeared: a Python set about 5 GB, a bytearray of flags 100 MB, a bit set 12.5 MB.
Chart— memory to record which of 100 million possible IDs appeared: a Python set about 5 GB, a bytearray of flags 100 MB, a bit set 12.5 MB.
python
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?

  1. It still works with 10⁸ bits
  2. Use a Python set; it fits
  3. 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
  4. Use a bytearray instead
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?

  1. Recursion depth reaches 10⁵, beyond Python's default limit of about 1,000; rewrite it with an explicit stack (or raise the limit carefully)
  2. The algorithm is too slow
  3. Graphs can't be searched in Python
  4. DFS needs O(n²) memory
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

  1. What does auxiliary space include and exclude?
  2. Walk Fibonacci from naive recursion to fast doubling, giving time and space for each.
  3. Why does the two-variable version need only O(1) values?
  4. Roughly how many bytes does one int cost in a Python list, a set, and a NumPy int64 array?
  5. When is a generator better than a list, and what does it save?
  6. When does a bit set beat a hash set, and when is it impossible?
Answers
  1. Extra structures, copies and the recursion stack; usually excludes the input and the required output (say so).
  2. 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.
  3. Each step depends only on the previous two values, so older ones can be discarded.
  4. About 36 bytes, about 50 to 100 bytes, 8 bytes.
  5. When you only need an aggregate or a single pass: it keeps O(1) values in memory instead of O(n).
  6. When values are small dense integers (index by value, one bit each); impossible when the value range is huge and sparse.