Space complexity — auxiliary vs total: Worked examples

Before anything, one plain-words reminder so no symbol is unearned:

The scenario matrix

Every space question you will ever meet falls into one of these cells. The Cell column is the label we tag each worked example with.

Cell	Case class	What makes it distinct	Typical auxiliary answer
A	Constant scratch, big input	fixed # of scalars, in-place	$O (1)$ aux, $O (n)$ total
B	Linear scratch you build	a new array of size $\propto n$	$O (n)$ aux
C	Recursion — linear depth	stack grows to depth $n$	$O (n)$ aux
D	Recursion — logarithmic depth	balanced divide-and-conquer	$O (lo g n)$ aux
E	Zero / degenerate input	$n = 0$ or $n = 1$ , empty structures	still valid — check the limit
F	2D table	grid of size $n \times m$	$O (n \cdot m)$ or $O (n^{2})$
G	Exponential output	must store $2^{n}$ things	$O (2^{n} \cdot n)$
H	The exam twist	time $\neq =$ space; branching recursion	depth, not node count
I	Real-world word problem	translate English → cells	depends — you decide

We now walk all nine cells with fully worked examples.

Figure — Space complexity — auxiliary vs total

The figure above is the mental model for the whole page: a table holds two piles of cells — the fixed input pile (blue, you can't shrink it) and the auxiliary pile (yellow, the part your cleverness controls). Recursion adds a stack of trays (red) that all sit on the table at once.

Cell A — Constant scratch, big input

Worked example A1 · Swap-based array reversal

def reverse(a):        # a has n elements
    i, j = 0, len(a)-1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1; j -= 1
    return a

Forecast: before reading on — is the auxiliary space $O (1)$ , $O (lo g n)$ , or $O (n)$ ? Write your guess.

Count the scratch cells. We create exactly two: i and j. Why this step? Auxiliary space = only cells we allocate ourselves. The array a was handed to us, so it is input, not scratch.
Ask: do those cells grow with $n$ ? No — always two, whether $n = 5$ or $n = 5, 000, 000$ . Why this step? $O (\cdot)$ measures growth. A count that never changes is $O (1)$ .
Conclude. Auxiliary $= O (1)$ . Total $=$ input $O (n)$ $+$ aux $O (1) = O (n)$ . Why this step? Total must include the $n$ -cell array we hold the entire time (see In-place algorithms).

Verify: For $n = 8$ the swap uses cells ${i, j} = 2$ , independent of $n$ . Doubling $n$ to $16$ still uses $2$ . Constant confirmed. ✅ This is the definition of an in-place algorithm.

Cell B — Linear scratch you build

Worked example B1 · Prefix-sum array

def prefix(a):              # a has n elements
    out = [0]*len(a)        # new array, size n
    run = 0
    for k in range(len(a)):
        run += a[k]
        out[k] = run
    return out

Forecast: guess the auxiliary space before the steps.

Find every allocation. out (length $n$ ) and one scalar run. Why this step? We separate the two kinds: an array that scales with $n$ , and a single scalar.
Combine. Cells $= n + 1$ . Why this step? Peak simultaneous usage adds them; both are alive during the whole loop.
Drop the constant. $n + 1 = O (n)$ . Why this step? The $+ 1$ is dwarfed by $n$ as $n$ grows; asymptotic notation drops it.

Verify: $n = 1000 \Rightarrow 1001$ cells; $n = 2000 \Rightarrow 2001$ . The ratio $2001/1001 \approx 2$ mirrors the doubling of $n$ — linear. ✅ Auxiliary $= O (n)$ , total $= O (n)$ .

Cell C — Recursion with linear depth

Worked example C1 · Recursive list sum (the sneaky

$O (n)$ )

def rec_sum(a, i=0):
    if i == len(a): return 0
    return a[i] + rec_sum(a, i+1)

Forecast: it declares no array and returns one number. Is it $O (1)$ auxiliary? Guess before the picture.

Look at the red tower in the figure. Each call to rec_sum is paused waiting for the deeper call to finish, so its stack frame stays alive. Why this step? A frame can only be freed after the call it is waiting on returns — see Recursion and the call stack.

Count peak simultaneous frames. The deepest call is at $i = n$ ; below it sit frames $i = n - 1, \dots, 0$ . That is $n + 1$ frames all alive at once. Why this step? Space is peak simultaneous cells, and here the peak is the moment just before the first return.

Multiply by frame size. Each frame holds $O (1)$ data, so total $= (n + 1) \times O (1) = O (n)$ . Why this step? Auxiliary space of recursion $=$ depth $\times$ frame size.

Verify: The iterative twin — a for loop with one accumulator — never stacks frames, so its auxiliary is $O (1)$ . Same answer, same time, but $O (n)$ vs $O (1)$ space. The recursion cost was real. ✅

Cell D — Recursion with logarithmic depth

Worked example D1 · Binary search (recursive) and Quick Sort's stack

def bsearch(a, lo, hi, key):
    if lo > hi: return -1
    mid = (lo+hi)//2
    if a[mid] == key: return mid
    if a[mid] < key:  return bsearch(a, mid+1, hi, key)
    else:             return bsearch(a, lo, mid-1, key)

Forecast: the array has $n$ elements. How deep does the recursion go — $n$ , $n$ , or $lo g_{2} n$ ?

Track the halving in the figure. Each call throws away half the remaining range. Why this step? If you halve $n$ repeatedly, the count of halvings to reach size $1$ is $lo g_{2} n$ .

Read off the depth. Number of nested calls $= lo g_{2} n$ , so at most $lo g_{2} n$ frames coexist. Why this step? Depth = number of times we can halve $n$ before hitting the base case.

Apply the recursion rule. Auxiliary $= lo g_{2} n \times O (1) = O (lo g n)$ . Why this step? Same "depth × frame size" law as Cell C, but the depth is now logarithmic.

Verify: For $n = 1024 = 2^{10}$ , depth $= lo g_{2} 1024 = 10$ . Ten frames, not a thousand. This is exactly why balanced Quick Sort uses $O (lo g n)$ average auxiliary — its partition is in-place and its recursion depth is $\approx lo g_{2} n$ when the pivots split evenly. ✅

Cell E — Zero and degenerate inputs

Worked example E1 · What happens at

$n = 0$ and $n = 1$ ? Take rec_sum (Cell C) and reverse (Cell A) at the edges.

Forecast: does an empty input use zero memory? Guess.

reverse on $n = 0$ . i, j = 0, -1; the loop body never runs. Cells used: still i,j $= 2$ . Why this step? Even with nothing to reverse, the two scalars are declared. Auxiliary stays $O (1)$ .
rec_sum on $n = 0$ . One call fires, immediately hits i == len(a) and returns. Peak depth $= 1$ frame. Why this step? The base case still occupies one frame; depth is $n + 1 = 1$ , consistent with $O (n)$ .
rec_sum on $n = 1$ . Depth $= 2$ (the $i = 0$ frame plus the base $i = 1$ frame). Why this step? Confirms the formula $depth = n + 1$ at the smallest non-trivial size.

Verify: Plug $n = 0$ into depth $n + 1 \Rightarrow 1$ frame ✅; plug $n = 1 \Rightarrow 2$ frames ✅. The formula is not broken by degenerate inputs — it degrades gracefully to a small constant.

Cell F — 2D tables

Worked example F1 · Edit-distance / dynamic-programming grid

def edit_table(s, t):        # len(s)=n, len(t)=m
    dp = [[0]*(m+1) for _ in range(n+1)]   # (n+1)x(m+1) grid
    ...
    return dp[n][m]

Forecast: if $n$ and $m$ are both the input, what is the auxiliary space?

Count grid cells. $(n + 1) \times (m + 1)$ integers. Why this step? A 2D table's cells multiply, they don't add.
Drop the $+ 1$ s. $(n + 1) (m + 1) = nm + n + m + 1 = O (nm)$ . Why this step? $nm$ dominates the linear and constant leftovers.
Special case $m = n$ . Then $O (nm) = O (n^{2})$ . Why this step? Square grids collapse to $O (n^{2})$ — rule of thumb #3 from the parent.

Verify: $n = m = 100 \Rightarrow 101 \times 101 = 10201$ cells $\approx 1 0^{4} = n^{2}$ . Doubling to $n = m = 200$ gives $201 \times 201 = 40401 \approx 4 \times 1 0^{4}$ — a 4× jump for a 2× input, the fingerprint of $O (n^{2})$ . ✅

Cell G — Exponential output

Worked example G1 · Store all subsets of an

$n$ -element set

def all_subsets(a):          # n elements
    result = [[]]
    for x in a:
        result += [subset+[x] for subset in result]  # doubles each round
    return result

Forecast: naive Fibonacci had exponential time but linear space. Does storing subsets have exponential space? Guess.

Count the subsets. A set of $n$ elements has $2^{n}$ subsets — each element is either in or out ( $2$ choices, $n$ times). Why this step? We are keeping every subset, so the output itself is $2^{n}$ items.
Weigh each subset. A subset can hold up to $n$ elements. Why this step? Space is total cells stored, not just the count of containers.
Multiply. $2^{n}$ subsets $\times$ up to $n$ elements $= O (2^{n} \cdot n)$ . Why this step? Every stored element is one live cell; they coexist because we return them all.

Verify: $n = 3 \Rightarrow 2^{3} = 8$ subsets: ${}, {a}, {b}, {c}, {ab}, {a c}, {b c}, {ab c}$ — total elements stored $= 0 + 1 + 1 + 1 + 2 + 2 + 2 + 3 = 12$ , and the bound $2^{n} \cdot n = 8 \cdot 3 = 24 \geq 12$ ✅. The bound holds; auxiliary $= O (2^{n} \cdot n)$ .

Cell H — The exam twist (time ≠ space)

Worked example H1 · Naive recursive Fibonacci

def fib(n):
    if n < 2: return n
    return fib(n-1) + fib(n-2)

Forecast: this makes about $2^{n}$ calls. Is its auxiliary space $O (2^{n})$ ? Commit to a guess.

Look at the recursion tree in the figure. Yes, there are $\approx 2^{n}$ nodes total — but they are not all alive at once. Why this step? Time counts every node ever visited; space counts only nodes alive simultaneously.

Trace one path down the tree. The computer explores depth-first: fib(n) → fib(n-1) → fib(n-2) → .... Only the frames along one root-to-leaf path are on the stack at any instant. Why this step? When a branch returns, its frame is freed before the sibling branch starts.

Measure the longest path. The deepest chain is $f ib (n) \to f ib (n - 1) \to \dots \to f ib (1)$ , length $n$ . So peak stack depth $= O (n)$ . Why this step? Depth of the tree, not size of the tree, sets the space.

Verify: time $= O (2^{n})$ (number of nodes), space $= O (n)$ (tree height). They genuinely differ. If a problem says "give the space complexity of naive fib," the answer is $O (n)$ , not $O (2^{n})$ . ✅

Cell I — Real-world word problem

Worked example I1 · "Deduplicate the guest list"

A hall system receives a list of $n$ guest IDs (some repeated) and must return the list of unique IDs. You add a hash set to track who you've already seen. What is your auxiliary space?

Forecast: guess $O (1)$ , $O (lo g n)$ , or $O (n)$ before translating.

Translate English to cells. "Track who you've seen" = a set that, in the worst case (all IDs distinct), holds all $n$ IDs. Why this step? Word problems must be reduced to what structure grows with $n$ .
Bound the worst case. If every guest is unique, the set stores $n$ entries; the output list also stores $n$ . Why this step? Space complexity is a worst-case guarantee unless told otherwise.
Add and drop constants. set $O (n)$ $+$ output $O (n)$ $= O (n)$ auxiliary. Why this step? $O (n) + O (n) = O (n)$ ; both are scratch you created.

Verify: $1000$ all-distinct guests ⇒ set of $1000$ + output of $1000$ = $2000$ cells $= O (n)$ . If instead there were only $10$ distinct IDs among the $1000$ , the set holds $10$ — still $O (distinct) \leq O (n)$ , the worst case. ✅ Auxiliary $= O (n)$ .

Every cell, in one glance

Formula Master table of what we proved

Cell	Example	Auxiliary	Reason
A	in-place reverse	$O (1)$	fixed scalar count
B	prefix-sum array	$O (n)$	one array $\propto n$
C	recursive sum	$O (n)$	stack depth $n$
D	binary search / Quick Sort	$O (lo g n)$	halving depth
E	empty/singleton input	$O (1)$ const	limits degrade gracefully
F	DP grid	$O (nm)$ / $O (n^{2})$	cells multiply
G	all subsets	$O (2^{n} \cdot n)$	store $2^{n}$ items of size $n$
H	naive `fib`	$O (n)$	tree height, not node count
I	dedup guest list	$O (n)$	worst-case distinct set

Active recall

Recall Which cell? Classify each on sight

A function builds an $n \times n$ matrix ::: Cell F → $O (n^{2})$ auxiliary. A function recurses by halving a sorted array ::: Cell D → $O (lo g n)$ . A branching recursion visiting $3^{n}$ nodes but only $n$ deep ::: Cell H → $O (n)$ space (height), not $O (3^{n})$ . Reversing a string in place with two pointers ::: Cell A → $O (1)$ . Generating every permutation and storing them all ::: Cell G-flavour → $O (n! \cdot n)$ (count × length). An algorithm called on an empty array ::: Cell E → still $O (1)$ constant, not zero.

Connections

Space complexity — auxiliary vs total (index 3.1.4) — the parent; definitions live there.
Recursion and the call stack — the source of Cells C, D, H.
Merge Sort / Quick Sort — $O (n)$ vs $O (lo g n)$ auxiliary, the D-vs-B contrast.
In-place algorithms — Cell A designed on purpose.
Time complexity — Big-O notation — the resource Cell H deliberately contrasts against.
Asymptotic notation — Big-O, Big-Omega, Big-Theta — why we drop the $+ 1$ s and constants.