Master

Space complexity

Time is only half the story. An algorithm also holds data at once, and that peak is its space cost. Measuring it is the same habit applied to memory.

What you will see

About 2 min of reading

Quick check

Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.

Try It

Name the space cost of small programs.

Running total of three.

a = [4, 7, 2] s = 0 for x in a: s += x print(s)

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Double a list of three.

a = [3, 1, 2] b = [x * 2 for x in a] print(b)

Before you run it, say out loud what it will print. Then open the answer.

What it prints

[6, 2, 4]

Grid of 3 by 3.

n = 3 table = [[0] * n for _ in range(n)] print(len(table), len(table[0]))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

3 3

Cache size for fib 6.

memo = {} def f(n): if n in memo: return memo[n] if n < 2: return n v = f(n - 1) + f(n - 2) memo[n] = v return v f(6) print(len(memo))

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Put it in order

Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.

Data Flow

Space cost is the peak memory held at one time. A running total is constant, a copy is linear, a grid is quadratic.

1 ask what is held

↓

2 count the live slots

↓

3 find the peak

↓

4 name the space class

Line by line

Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.

a = [4, 7, 2] sets nothing on screen

s = 0 sets nothing on screen

for x in a: sets nothing on screen

s += x sets nothing on screen

print(s) 13

Why this works

Peak, not total

Space cost is the maximum held at one moment. Allocation that is freed later does not raise the peak.

Space has its own dials

In place work, streaming, and dropping a cache all trade time for space. The class is chosen, not inherited.

Examples

Constant space

a = [4, 7, 2]
s = 0
for x in a:
    s += x
print(s)

Only one running total is held whatever the length. That is constant space.

Linear space

a = [3, 1, 2]
b = [x * 2 for x in a]
print(b)

The new list holds n items. Space grows with the input, so it is linear.

A copy is linear space

a = [1, 2, 3]
b = a[:]
print(len(b))

A full copy stores n more slots. The time and the space are both linear here.

Recursion holds a stack

def total(a):
    if not a:
        return 0
    return a[0] + total(a[1:])
print(total([1, 2, 3]))

Each call keeps a frame, so depth n costs n frames. The slicing also copies, adding more.

A table is quadratic

n = 3
table = [[0] * n for _ in range(n)]
print(len(table), len(table[0]))

A grid of n by n holds n squared cells. Space can be a class above the time.

In place saves space

a = [3, 1, 2]
a.sort()
print(a)

Sorting the list itself keeps no second list. The space stays small even though time is n log n.

Peak is what counts

a = list(range(4))
b = a[:]
del a
print(len(b))

Space is the most held at one time, not the total ever allocated. Freeing helps the peak.

Cache trades space

memo = {}
def f(n):
    if n in memo:
        return memo[n]
    if n < 2:
        return n
    v = f(n - 1) + f(n - 2)
    memo[n] = v
    return v
print(len(memo))

The cache stores one entry per state. Space n buys linear time.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← Reading real costs

Previous Lesson

Reading real costs

Next Lesson

You cannot beat the bound

You cannot beat the bound →