In the previous lesson we learned to count steps; in this one we will learn to count memory. We closed 02-01 with an outstanding debt: we sped up transfers from O(n²) to O(n) by building a set, and we said the price was "extra memory" without quantifying it. Space complexity measures exactly that: how much additional memory an algorithm needs as a function of the size of its input. It matters because memory, like time, is a finite resource — on a server handling thousands of simultaneous RutaBus requests, an algorithm that copies the entire stop network per request can bring the machine down even if it is lightning fast — and because, as we will see, time and space can be traded: often the way to gain speed is to spend memory, and it pays to know how much.
The good news: the method is the same line-by-line analysis from 02-01 and it is expressed with the same asymptotic notation from 01-03 (O as an upper bound on growth — here, of memory consumption). Only the question changes: instead of "how many times does this line run?", we ask "how much live memory does this algorithm end up accumulating?".
Contents
- What counts as space: total vs auxiliary
- Line-by-line memory analysis
- Copies vs references in Python
- The space cost of recursion: the call stack
- The time ↔ space trade-off: a stop index for RutaBus
- Space cost of Python's data structures
What counts as space: total vs auxiliary
The memory an algorithm uses has two components:
- Input space: the memory occupied by the data it receives (the list of stops, the schedules...). The algorithm can do nothing to reduce it: it is given.
- Auxiliary space: the additional memory the algorithm allocates in order to work — variables, temporary structures, copies, the call stack.
Two measures come out of this:
| Measure | What it includes | Example: searching n stops with 3 variables |
|---|---|---|
| Total space | Input + auxiliary | O(n) — the input dominates |
| Auxiliary space | Only what the algorithm allocates | O(1) — three variables |
The useful measure for comparing algorithms is auxiliary space, because the input is the same for every algorithm that solves the same problem. When we say "this algorithm is O(1) in space" we will always mean auxiliary space, and that is the convention we will use for the rest of the course. (When you read documentation, check which of the two measures it uses: the confusion is frequent.)
One more nuance, parallel to the one in the previous lesson: the relevant space is the maximum simultaneous amount (the peak), not the accumulated total. If an algorithm creates a temporary list of n elements, frees it and creates another, its auxiliary space is O(n), not O(2n)... which would be O(n) anyway — but the nuance matters when structures coexist: two lists of n elements alive at the same time are O(n); one list of n² elements is O(n²).
Line-by-line memory analysis
Starting rules, analogous to the time ones:
- A scalar variable (a number, a boolean, a reference to an object) takes O(1): its size does not depend on n.
- A data structure takes space proportional to its elements: a list with n stops is O(n).
- The auxiliary space of an algorithm is the peak of live auxiliary memory during its execution.
Let's analyze the RutaBus functions we already know:
def nearest_stop(user_x, user_y, stops):
best_stop = stops[0] # O(1): reference to a dict that ALREADY exists
best_distance = distance(...) # O(1): a number
for stop in stops[1:]: # O(n)!: the slice creates a new list
d = distance(...) # O(1): a number (reused on each pass)
...
return best_stopSurprise: the function that was a clean O(n) in time has a space cost of O(n) auxiliary... because of the very same slice that already caused us trouble in 02-01. stops[1:] builds a new list with n−1 references. If we iterated with indices (for i in range(1, len(stops))) or with islice, the auxiliary space would be O(1): three scalar variables reused on every pass. Notice that d does not accumulate: on each iteration it overwrites its previous value, so it counts only once.
Second example, the set version from the previous lesson:
def transfers_v2(line_a, line_b):
stops_b = set(line_b) # O(n): structure with n elements
common = [] # O(k): will grow up to k common stops (k <= n)
for stop in line_a:
if stop in stops_b: # O(1) in time... thanks to the O(n) in space
common.append(stop)
return commonAuxiliary space: O(n) for the set + O(k) for the result → O(n). Here it is, finally quantified, the bill for the speed-up from 02-01: we went from O(n²) time / O(1) space to O(n) time / O(n) space. That exchange has a name and its own section below.
Convention: when the result that is returned is necessarily large (like
common), some analyses exclude it from the auxiliary space ("output space"). Be aware of the convention and state it; in this course we will include it, unless noted otherwise.
Copies vs references in Python
To count memory in Python you must know one fundamental fact about the language: assigning is not copying.
line_l1 = ["Main Square", "Central Hospital", "North Station", "River Park"]
alias = line_l1 # O(1): just one more reference to THE SAME list
copy_ = list(line_l1) # O(n): new list with n copied references
slice_ = line_l1[1:3] # O(k): new list with the k elements of the rangealias = line_l1duplicates nothing: both variables point to the same object (check it:alias is line_l1→True; if you doalias.append(...),line_l1sees it too). Cost: O(1).list(line_l1),line_l1.copy()and slices create new lists: O(n) or proportional to the range. (It is a shallow copy: the references are copied, not the objects they point to — enough for our order-of-growth analysis.)- Passing a list as an argument to a function is like an assignment: the reference is passed, O(1). That is why calling
nearest_stop(x, y, stops)does not duplicate the network; what triggers the spending is whatever the function does inside (slices, copies).
| Operation | Creates a new object? | Space cost |
|---|---|---|
b = a |
No (reference) | O(1) |
| Passing an argument to a function | No (reference) | O(1) |
a[i], a[i] = v |
No | O(1) |
a[1:], a.copy(), list(a) |
Yes | O(n) |
a + b (lists or strings) |
Yes | O(len(a)+len(b)) |
sorted(a) |
Yes (new list) | O(n) |
a.sort() |
No (sorts in place) | O(1)* auxiliary (*approx.; Python's actual algorithm uses a bit more) |
The pair sorted(a) / a.sort() is the perfect example of how the same task can be offered in a "spend memory and keep the original" version or an in place one: choosing well is applied space analysis.
The space cost of recursion: the call stack
In 01-02 we saw that every pending recursive call lives on the call stack. That has a cost the code does not show: each active call occupies a frame with its local variables and the return address. Therefore:
Space of a recursion = (maximum stack depth) × (space of each frame)
Let's revisit count_stops_recursive:
def count_stops_recursive(stops):
if not stops:
return 0
return 1 + count_stops_recursive(stops[1:])While the call on [] (the deepest one) is running, all the previous ones are still alive, waiting for its result to add 1 to it: there are n+1 frames stacked at once. Depth O(n) × frame O(1) = O(n) of stack. And in this particular implementation there is more: each level created its slice stops[1:], and that list stays alive while its frame waits — n lists of sizes n−1, n−2, ..., 0 coexisting: arithmetic sum → O(n²) auxiliary in total. The same function, measured with both yardsticks:
Version of count_stops |
Time (02-01) | Auxiliary space |
|---|---|---|
| Iterative | O(n) | O(1) |
| Recursive with slices (ours) | O(n²) | O(n²) |
| Recursive with an index (no slices) | O(n) | O(n) — the stack alone |
Two practical lessons:
- A recursion never goes below O(depth) in space, even if it creates no structure at all: the stack counts. An equivalent iterative algorithm usually stays at O(1).
- In Python this is not theoretical: the stack has a limit (~1000 levels by default;
RecursionError: maximum recursion depth exceededwhen you cross it).count_stops_recursiveon the complete network of a city with 3,000 stops does not even finish. For small, bounded depths (log n, as in the algorithms of Module 3) recursion is safe and elegant; for depth n on large inputs, in Python it is better to iterate.
The time ↔ space trade-off: a stop index for RutaBus
A real RutaBus case: the app constantly looks up a stop's data by its name (to render its info card, its schedules, its connections). With the usual stops list, every lookup is a linear search:
def stop_data(stops, name): # time O(n), space O(1)
for stop in stops:
if stop["name"] == name:
return stop
return NoneIf the main screen performs 50 lookups and the network has 3,000 stops, that is 150,000 comparisons per user and screen. The alternative: precompute an index — a dictionary mapping each name to its stop — once, and look up in O(1):
def build_index(stops):
"""Runs ONCE when the network is loaded. Time O(n), space O(n)."""
index = {}
for stop in stops:
index[stop["name"]] = stop # reference, not copy: O(1) per entry
return index
index = build_index(stops)
def stop_data_v2(index, name): # time O(1), space O(1)
return index.get(name) # hash lookup: O(1)Let's compare the two strategies for q lookups over n stops:
| Strategy | Preparation | Cost per lookup | q lookups | Extra memory |
|---|---|---|---|---|
| Linear search | — | O(n) | O(q·n) | O(1) |
| Index (dict) | O(n) once | O(1) | O(n + q) | O(n) |
This is the time ↔ space trade-off in its purest form: we have bought speed by paying with memory. Note that the index stores references to the same dictionaries in the list (section 3): the overhead is one dictionary entry per stop, O(n), not a duplication of all the data. Is it worth it? Almost always, as long as q is large and n fits in memory — which is the typical case for an app like RutaBus. But it is neither free nor automatic: on an embedded device with minimal memory, or with a network that does not fit in RAM, the "slow but frugal" linear search may be the right choice. Space analysis exists precisely so that this decision is made with numbers, not hunches.
Hold on to this idea of "spending memory to avoid repeating work": it will reappear, with a name of its own and in a big way, in lesson 03-03.
Space cost of Python's data structures
A closing parallel to 02-01: the reference table, now in memory terms, for n elements:
| Structure | Space | Practical notes |
|---|---|---|
list |
O(n) | Reserves some extra room to grow (small constant) |
tuple |
O(n) | Immutable; somewhat more compact than the equivalent list |
dict |
O(n) | Stores key + value + hash table: larger constant than a list |
set |
O(n) | Like the dict, without values |
str |
O(n) | Immutable: every "modification" creates a new one (remember 02-01) |
| generator | O(1) | Produces the elements one at a time, without materializing the collection |
The star row is the last one. Compare:
squares_list = [d * d for d in range(1_000_000)] # list: O(n) — a million numbers in RAM
squares_gen = (d * d for d in range(1_000_000)) # generator: O(1) — a "recipe" that produces themThe first line materializes the million values; the second creates a tiny object that hands them out on demand (as it is iterated). If you are only going to walk through the values once — sum them, find the maximum, filter them — the generator gives the same result with O(1) auxiliary space: sum(d * d for d in range(1_000_000)) never has the million numbers alive at once. Its limits: it cannot be indexed, measured with len, or traversed twice.
These figures are orders of growth; Python's actual constants (a small int takes 28 bytes, a dict has per-entry overhead, etc.) and the techniques to reduce them — __slots__, array, stream processing — belong to lesson 05-02 (Efficient Memory Usage). Here it is enough to know what grows and how.
Common Mistakes and Tips
- Confusing total space with auxiliary space: "this function receives a list of n stops, therefore it is O(n)" — no: the input is not charged to the algorithm. Ask yourself what memory it adds.
- Counting as a copy what is a reference (and vice versa):
b = aand passing arguments do not copy (O(1));a[1:],a.copy(),a + bandsorted(a)do (O(n)). This is the number one mistake when analyzing space in Python. - Forgetting the recursion stack: a recursive function "with no variables" is not O(1): it costs at least O(depth). And in Python, depth n with large n is not just expensive: it is a
RecursionError. - Adding peaks that do not coincide in time: auxiliary space is the simultaneous maximum. Two temporaries of size n used one after the other are still O(n).
- Optimizing memory that doesn't matter: if n is 200 stops, an O(n) index is negligible and the debate is pointless. Space analysis decides when n is large or memory is scarce; otherwise, code clarity comes first.
- Tip: for any algorithm, write down its pair of costs "time / space" (for example, O(n) / O(1)). Getting used to seeing them together will make you spot trade-offs — and prepares you to read them in any library's documentation.
Exercises
Exercise 1. Determine the auxiliary space (and, while you are at it, the time) of these two versions of a RutaBus utility that checks whether all the arrivals at a stop are earlier than a cutoff time:
# Version A
def all_before_a(schedules, limit):
earlier = [h for h in schedules if h < limit]
return len(earlier) == len(schedules)
# Version B
def all_before_b(schedules, limit):
for h in schedules:
if h >= limit:
return False
return TrueExercise 2. This recursive function computes the total duration of a trip by adding up the minutes of each segment. Give its space cost as written, explain where it comes from, and write a version with O(1) auxiliary space.
def total_duration(segments):
"""segments: list of durations in minutes, e.g. [4, 6, 3, 5]."""
if not segments:
return 0
return segments[0] + total_duration(segments[1:])Exercise 3. RutaBus needs to answer many queries of the form "does line X pass through stop Y?". Today this is solved with stop in lines[x] over lists of stops. Propose a precomputed structure that answers in O(1), give its space cost, and reason about the scenario in which it would not be worth using.
Solutions
Solution 1. Version A builds, with the list comprehension, a new list with up to n schedule entries: auxiliary space O(n) (and time O(n)). Version B uses a single loop variable that is reused: auxiliary space O(1), time O(n) — and even better in practice, because it bails out as soon as it finds a late arrival (we will formalize that difference between scenarios in 02-03). Same time complexity, different space complexity: B is strictly preferable. Note: all(h < limit for h in schedules) is the idiomatic form — the generator keeps the space at O(1).
Solution 2. Stack depth: n+1 frames alive at once → O(n) from the stack alone. In addition, each level creates the slice segments[1:], which stays alive while its frame waits: sizes n−1, n−2, ..., 0 simultaneously → arithmetic sum → O(n²) auxiliary in total (and O(n²) time, as we saw in 02-01). Iterative version with O(1) auxiliary space:
def total_duration_v2(segments):
total = 0 # O(1)
for minutes in segments: # the variable is reused on each pass
total += minutes
return total(Python's sum(segments) does exactly this.)
Solution 3. Precompute a dictionary of sets: stops_by_line = {"L1": {"Main Square", ...}, "L2": {...}, ...}. The query stop in stops_by_line["L1"] is O(1). Space cost: one entry per line-stop pair → O(L · p) where L is the number of lines and p the number of stops per line — that is, proportional to the total size of the network, O(n). It would not be worth it if: (a) queries are very rare (building it — and keeping it in sync when the network changes — never pays for itself), or (b) memory is the critical resource (embedded device, huge networks). It is the same time ↔ space trade-off as the stop index: buying speed with memory only pays off if the speed gets used and the memory is to spare.
Conclusion
We now know how to measure the other half of an algorithm's bill. We have distinguished total space from auxiliary space (the measure that compares algorithms), we have applied line-by-line analysis to memory — scalars O(1), structures O(n), and in Python the crucial distinction between references (free) and copies (O(n)) —, we have discovered that recursion pays an invisible O(depth) cost on the stack (with RecursionError as a very visible reminder in Python), and we have finally quantified the time ↔ space trade-off with the RutaBus stop index: O(1) speed bought with O(n) memory. The structure table — with the generator as the O(1) champion — completes our toolbox; the techniques for seriously squeezing memory are left for lesson 05-02.
With time and space we can now fill in the cost sheet of any algorithm... with one pending nuance that has been peeking out all lesson long: we said "in the worst case" when measuring times, and in the exercises we ran into functions that sometimes finish on the first try and sometimes traverse everything. What about the favorable cases? And the "typical" case? Are those who claim that linear search "usually" costs half of it lying? In the next lesson (02-03) we will sort it all out: best case, worst case and average case, when each one matters and how they truly relate — for real — to the O, Ω and Θ notations.