Space complexity: memory, recursion, streaming

Space complexity is the same idea for memory: how much extra memory your code needs as the input grows. In data engineering this is often the limit you hit first.

Count only the extra memory your code creates, not the input you were given. A loop that keeps one running total uses O(1) extra space whether the file has 10 rows or 10 crore. Copying every row into a list uses O(n). A recursive function that calls itself n levels deep uses O(n) as well, because every unfinished call waits on the stack.

import tracemalloc

def peak_kb(fn):
    tracemalloc.start()
    fn()
    _, peak = tracemalloc.get_traced_memory()
    tracemalloc.stop()
    return peak // 1024

n = 1_000_000
as_list = lambda: sum([x * 2 for x in range(n)])  # a list
as_gen = lambda: sum(x * 2 for x in range(n))     # streams
print("list:", peak_kb(as_list), "KB extra")
print("gen: ", peak_kb(as_gen), "KB extra")

list: 39496 KB extra
gen:  0 KB extra

Same answer, same O(n) time. The list version holds a million numbers at once; the generator holds one. On a file bigger than RAM, only the second one finishes.

import sys

def total(xs, i=0):        # recursion: O(n) stack
    if i == len(xs):
        return 0
    return xs[i] + total(xs, i + 1)

print(sys.getrecursionlimit())
print(total(list(range(500))))
print(total(list(range(5_000))))

1000
124750
RecursionError: maximum recursion depth exceeded

def total(xs):                 # loop: O(1) extra
    s = 0
    for x in xs:
        s += x
    return s

print(total(list(range(5_000))))
print(total(range(10_000_000)))

12497500
49999995000000

CPython stops recursion at about 1,000 levels by default, so deep recursion on real data crashes. Python does not optimise tail calls: turn deep recursion into a loop or an explicit stack.