Space complexity and measuring memory

Time is not the only cost of an algorithm. Memory runs out too, and on a phone, in a browser tab or in a server that handles thousands of requests at once it can run out first. Space complexity describes how the memory an algorithm needs grows with its input, with the same notation as running time; this lesson shows what to count and how to measure it in Python.

Input, auxiliary and output space

Split the memory an algorithm touches into three parts:

• Input space holds the input itself. Every algorithm needs it, so it says nothing about the algorithm.
• Auxiliary space is the extra memory the algorithm uses while it works: variables, temporary lists, sets, and the call stack of a recursive function.
• Output space holds the result, when the result is new data rather than a yes, a no or one number.

When a lesson says an algorithm “uses O(1) space”, it means auxiliary space unless it says otherwise. An algorithm that works in place changes its input instead of building a new copy and needs only O(1) auxiliary space, or sometimes O(log n) for a recursion that halves its input. Reversing a list shows the difference: items.reverse() reverses the list in place, while items[::-1] builds a second list of n references.

Measuring memory in Python

Python gives you two tools, and they answer different questions.

• sys.getsizeof(x) returns the size of the object x alone, not of the objects it refers to.
• The tracemalloc module records the memory blocks Python allocates while it is tracing; tracemalloc.get_traced_memory() returns the current total and the peak, the most there was at any one moment.

import sys
import tracemalloc
from array import array

# 1. sys.getsizeof() measures one object only, not the objects it refers to.
numbers = list(range(1_000, 2_000))
print(f"sys.getsizeof(numbers):          {sys.getsizeof(numbers):>7,} bytes for the list and its 1,000 references")
print(f"sum of sys.getsizeof() of items: {sum(sys.getsizeof(x) for x in numbers):>7,} bytes for the 1,000 int objects")


# 2. tracemalloc counts every block Python allocates while it is tracing.
def peak_mb(build):
    """Most memory, in megabytes, that Python had allocated at one time while build() ran."""
    tracemalloc.start()
    data = build()
    peak = tracemalloc.get_traced_memory()[1]
    tracemalloc.stop()
    del data
    return peak / 1_000_000


N = 1_000_000
print(f"\nPeak memory to build {N:,} values:")
for label, build in [
    ("list(range(N))", lambda: list(range(N))),
    ("array('q', range(N))", lambda: array("q", range(N))),
    ("[i % 256 for i in range(N)]", lambda: [i % 256 for i in range(N)]),
    ("bytes(i % 256 for i in range(N))", lambda: bytes(i % 256 for i in range(N))),
]:
    print(f"  {label:<34} {peak_mb(build):5.1f} MB")

sys.getsizeof(numbers):            8,056 bytes for the list and its 1,000 references
sum of sys.getsizeof() of items:  28,000 bytes for the 1,000 int objects

Peak memory to build 1,000,000 values:
  list(range(N))                      40.0 MB
  array('q', range(N))                 8.2 MB
  [i % 256 for i in range(N)]          8.4 MB
  bytes(i % 256 for i in range(N))     1.0 MB

sys.getsizeof(numbers):            4,028 bytes for the list and its 1,000 references
sum of sys.getsizeof() of items:  16,000 bytes for the 1,000 int objects

Peak memory to build 1,000,000 values:
  list(range(N))                      20.0 MB
  array('q', range(N))                 8.2 MB
  [i % 256 for i in range(N)]          4.2 MB
  bytes(i % 256 for i in range(N))     1.0 MB

The first two lines show what “shallow” means: sys.getsizeof() counts the list and its 1,000 references, 8 bytes each on this 64-bit computer, and nothing of the 1,000 int objects those references point to, which take more than three times as much again.

The second part shows why the type of container matters as much as the algorithm:

• list(range(N)) peaked at about 40 MB: 8 MB for a million references, and about 32 MB for the million separate int objects they point to. tracemalloc counts the whole 32-byte block that holds each one, a little more than the 28 bytes that sys.getsizeof() reports for the object itself.
• array('q', ...) stores the values themselves, as 8-byte C integers side by side, in a little over 8 MB.
• The list of a million numbers from 0 to 255 takes little more than the 8 MB of its references, because CPython keeps one shared object for each whole number from −5 to 256 and hands out references to it instead of making new ones.
• bytes stores each value in a single byte, which is enough for numbers from 0 to 255: 1 MB.

The recursion stack is memory too

A recursive function that has not returned yet keeps its frame, its arguments and local variables, on the call stack. Summing a linked list recursively makes one call per node, and all of them wait at once:

import sys


class Node:
    """One item of a singly linked list: a value and the next node (None at the end)."""

    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node


def build(n):
    head = None
    for value in range(n, 0, -1):
        head = Node(value, head)
    return head


def sum_iterative(node):
    total = 0
    while node is not None:  # one frame, however long the list: O(1) extra space
        total += node.value
        node = node.next
    return total


def sum_recursive(node, depth=1, deepest=None):
    """The same sum; deepest[0] records how many calls were waiting at the deepest point."""
    deepest[0] = max(deepest[0], depth)
    if node is None:
        return 0
    return node.value + sum_recursive(node.next, depth + 1, deepest)


print("recursion limit:", sys.getrecursionlimit())
for n in (10, 100, 900):
    head = build(n)
    deepest = [0]
    assert sum_recursive(head, deepest=deepest) == sum_iterative(head) == n * (n + 1) // 2
    print(f"n = {n:>4}: both sums agree; the recursive one had {deepest[0]:>3} calls waiting at once")

head = build(5_000)
print("n = 5000: iterative sum", sum_iterative(head))
try:
    sum_recursive(head, deepest=[0])
except RecursionError as error:
    print("n = 5000: recursive sum failed:", error)

recursion limit: 1000
n =   10: both sums agree; the recursive one had  11 calls waiting at once
n =  100: both sums agree; the recursive one had 101 calls waiting at once
n =  900: both sums agree; the recursive one had 901 calls waiting at once
n = 5000: iterative sum 12502500
n = 5000: recursive sum failed: maximum recursion depth exceeded

Both functions do the same additions in the same time, O(n). The iterative one keeps a total and one node reference, so its auxiliary space is O(1). The recursive one has n + 1 calls waiting at its deepest point (one per node, plus the call that reaches the end), so its auxiliary space is O(n), although it creates no list at all. Python limits how deep the stack may grow, so that runaway recursion stops with an error instead of crashing the interpreter. The limit here was 1,000 frames, which is why the list of 5,000 nodes fails with RecursionError, while the loop sums it without trouble.

When a recursion’s depth grows with n, write the loop instead, or make sure the depth only grows like log n, as in a recursion that halves its input on every call.

Trading memory for time

Many fast algorithms are fast because they store something. Prefix sums are a clear case: keep the running totals of a list, and the sum of any range becomes one subtraction.

import random
from itertools import accumulate

rng = random.Random(9)
n, q = 1_000, 1_000
values = [rng.randint(1, 100) for _ in range(n)]
queries = [sorted(rng.sample(range(n + 1), 2)) for _ in range(q)]  # ranges lo up to, not including, hi

# 1. No extra memory: add up each range again.
additions = 0
slow = []
for lo, hi in queries:
    total = 0
    for i in range(lo, hi):
        total += values[i]
        additions += 1
    slow.append(total)

# 2. n + 1 extra numbers: prefix[i] is values[0] + ... + values[i - 1].
prefix = [0, *accumulate(values)]
fast = [prefix[hi] - prefix[lo] for lo, hi in queries]  # one subtraction per query

assert fast == slow
print(f"recomputing each range: {additions:>7,} additions, no extra list")
print(f"prefix sums:            {n - 1:>7,} additions to build them, then {q:,} subtractions; {len(prefix):,} numbers stored")

recomputing each range: 338,873 additions, no extra list
prefix sums:                999 additions to build them, then 1,000 subtractions; 1,001 numbers stored

The same trade appears again and again: the set that found duplicates in one pass, tables that remember the answers to smaller problems in dynamic programming, indexes in databases. The CS2023 curriculum names time and space trade-offs as a core topic of complexity analysis. The trade also runs the other way: the exercise below keeps the time the same and cuts the memory from O(n²) to O(n), by handing out results one at a time instead of storing them all.

Key takeaways

• Count auxiliary space, the memory an algorithm adds on top of its input and output; “in place” means O(1) of it, or O(log n) for a halving recursion.
• sys.getsizeof() measures one object without the objects it refers to; tracemalloc measures everything Python allocates, including the peak.
• A list of numbers stores references to separate int objects (about 40 MB for a million on 64-bit CPython), while array('q') stores 8-byte values (about 8 MB).
• Every call a recursion keeps waiting is memory: recursion over n items needs O(n) stack, and Python stops it at its recursion limit.
• Prefix sums, hash sets and memoisation spend memory to save time; a generator can save memory without changing how the running time grows.