Space complexity — auxiliary vs total: Visual walkthrough

We build everything from zero. No prior notation is assumed.

Step 1 — What a "memory cell" even is

WHAT. Before we can count memory we must agree on the unit. Our unit is one box.

WHY. Space complexity is nothing but "how many boxes are alive at the same moment, as the input grows." If we can draw the boxes, we can count them. Everything else on this page is drawing boxes.

PICTURE. Below: a variable is a labelled box. The name (i) is the label, the value (0) is what sits inside. The red box is the one we will track as our "key" object throughout.

Figure — Space complexity — auxiliary vs total

Step 2 — Two piles of boxes: input vs scratch

WHAT. We separate every box a running program holds into exactly two piles.

WHY. The parent note's whole point is that these two piles are counted differently. The input pile was handed to you — you cannot shrink it. The scratch pile you conjured yourself — this is the pile that measures how clever the algorithm is. Naming the piles now means every later figure just sorts boxes into one pile or the other.

PICTURE. The list a of $n$ boxes sits in the input pile (black). The two loop variables i, j sit in the scratch pile — and one of them, our tracked cell, is red.

Step 3 — A flat program: scratch that does NOT grow

WHAT. Run in-place reversal and freeze the memory at three moments. Program:

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

WHY. We want to see what " $O (1)$ auxiliary" looks like as a picture. The claim from the parent is that reversal adds only a constant number of scratch boxes. A claim about growth can only be trusted if we compare two different input sizes — so we draw $n = 4$ and $n = 8$ side by side and check the scratch pile does not change.

PICTURE. Top row: $n = 4$ , scratch pile = {i, j} = 2 boxes. Bottom row: $n = 8$ , scratch pile still = 2 boxes. The input pile doubled; the red-outlined scratch pile did not move.

Step 4 — Scratch that DOES grow with $n$

WHAT. Now a program whose scratch pile grows. Build a copy:

def squares(a):
    out = [x*x for x in a]   # new list, n boxes
    return out

WHY. Step 3 showed a flat scratch pile. To understand the formula we must also see a scratch pile that tracks $n$ — otherwise " $O (n)$ auxiliary" is just words. Draw $n = 4$ and $n = 8$ again; this time watch the scratch pile grow in lockstep with the input.

PICTURE. Input pile a (black) and scratch pile out (red) are the same height, and both double when $n$ doubles.

Step 5 — The sneaky pile: recursion's hidden boxes

WHAT. The most-missed case. A recursive sum:

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

It declares no array. It returns one number. It looks like $O (1)$ .

WHY. We must expose the invisible pile. Each time a function calls another (or itself) before finishing, the paused call is not deleted — it is set aside on a stack, still holding its own boxes, waiting for the inner call to come back. See Recursion and the call stack. To see this, we draw every paused call as its own little tray, stacked, all alive at the same instant.

PICTURE. Five trays stacked for $n = 4$ : rec_sum(a,0) waiting on rec_sum(a,1) waiting on … The whole tower is alive at the deepest moment (red = the tray at the bottom, the one currently running). No returns have happened yet.

Step 6 — Same time, different space: Merge vs Quick

WHAT. Two sorts, both $O (n lo g n)$ time, but different auxiliary towers.

WHY. This is the payoff: space is a separate resource from time (contrast with Time complexity — Big-O notation). Drawing the two recursion towers side by side shows why they differ — Merge Sort rents a full-width temp array to merge; Quick Sort partitions in place, so only the tower's height costs memory.

PICTURE. Left: Merge Sort — a red temp array of width $n$ living beside the recursion. Right: Quick Sort — no temp array, just a short tower of height $lo g n$ (balanced case), red-outlined.

Step 7 — Degenerate & edge cases (nobody may be surprised)

WHAT. The corners where the rule bites unexpectedly. We draw four:

WHY. The contract: the reader must never hit a scenario we did not show. Each corner below trips someone up in an interview.

PICTURE. Four mini-panels:

Empty input ( $n = 0$ ): input pile has 0 boxes, but scratch still needs its constant boxes → $S_{aux} = O (1)$ does not become 0.
Fixed 26-box frequency array: 26 never depends on $n$ → $O (1)$ , even though 26 > small $n$ .
Unbalanced Quick Sort (already-sorted input): the tower is not $lo g n$ tall but $n$ tall → worst-case $O (n)$ auxiliary, the red tall tower.
All subsets of $n$ elements: $2^{n}$ subsets each up to $n$ long → $O (2^{n} \cdot n)$ space, distinct from its time.

The one-picture summary

Every idea on this page is one question — "how many boxes are alive at the peak moment, and which pile are they in?" This final figure lays the whole derivation on one line: flat scratch ( $O (1)$ ) → shadow scratch ( $O (n)$ ) → recursion tower ( $O (n)$ ) → the total formula.

Recall Feynman retelling — the whole walk in plain words

You get a box of LEGO — that is the input pile, and you cannot make it smaller. To build, you grab a little side-tray for extra pieces — that is the scratch pile, and how small you keep it is what makes you a clever builder.

Sometimes your tray stays tiny no matter how big the box (reversing a list — just two counters): that is $O (1)$ scratch. Sometimes your tray grows exactly as big as the box (copying every piece into a new pile): that is $O (n)$ scratch.

The sneaky part is when you start a side-project inside a side-project inside another — recursion. Each unfinished one keeps its own tray on the table at the same time. Stack them $n$ deep and you have $n$ trays out — $O (n)$ — even though each one looks tiny and returns just one number.

Merge Sort rents one big extra tray ( $O (n)$ ); Quick Sort shuffles the pieces right in the original box and only pays for the tower of unfinished calls ( $O (lo g n)$ when the splits are even, but a tall $O (n)$ tower if they are lopsided).

To count any program's space, freeze time at the busiest moment, count every box on the table, and sort them into "given" and "mine." Add the piles. That sum is total; the "mine" pile alone is auxiliary. That is the entire formula $S_{total} = S_{input} + S_{aux}$ , and now you have watched it happen.

Connections

Parent — Auxiliary vs Total
Recursion and the call stack — where the sneaky tower comes from.
Merge Sort / Quick Sort — the $O (n)$ vs $O (lo g n)$ scratch contrast.
In-place algorithms — the art of a tiny scratch pile.
Time complexity — Big-O notation — same Big-O machine, different resource.
Asymptotic notation — Big-O, Big-Omega, Big-Theta — why $O (2 n) = O (n)$ .