Space complexity — auxiliary vs total: Question bank

Before you start, load the two definitions into memory so every trap has something to bite against:

True or false — justify

Every item below is a statement. Decide true or false and give the reason — a bare verdict scores zero on this page.

An algorithm with

O (1)

auxiliary space always has

O (1)

total space.

False — total also counts the input, so holding an

n

-sized array makes total

O (n)

even if you allocate zero scratch. Auxiliary and total only agree when the input is

O (1)

Merge Sort and Quick Sort have the same time complexity, so they have the same space complexity.

False — both are

O (n lo g n)

time, but Merge Sort needs an

O (n)

temp array while balanced Quick Sort uses only its

O (lo g n)

recursion stack. Time equality says nothing about space.

A recursive function that declares just one local variable and returns a single integer uses

O (1)

auxiliary space.

False — each pending call keeps its own frame alive on the stack; if recursion goes

n

deep,

n

frames coexist, giving

O (n)

auxiliary. The single variable is per frame, not total.

Reducing auxiliary space from

O (n)

O (1)

always reduces total space.

False — if the input is already

O (n)

, total stays

O (n)

because the input dominates. Shrinking scratch below the input size cannot lower the total order.

Naive recursive Fibonacci has

O (2^{n})

space complexity because it makes exponentially many calls.

False — the calls happen over time, not simultaneously. Only one root-to-leaf path is live at once, so peak stack depth (and auxiliary space) is

O (n)

, while

O (2^{n})

is its time.

An in-place algorithm uses no memory beyond the input.

False — "in-place" means

O (1)

auxiliary (a constant amount of scratch), not literally zero. A few index variables are allowed.

Two algorithms with the same auxiliary space always have the same total space.

True only if they take the same-sized input — total is input + aux, so equal aux plus equal input space gives equal total. Different input sizes break this.

Constants are dropped in Big-O, so allocating three arrays of size

n

is the same asymptotic auxiliary space as allocating one.

True —

3 n

and

n

are both

O (n)

; Big-O absorbs the constant factor 3. The number of arrays matters for the machine, not for the order.

Spot the error

Each line states a (wrong) claim someone confidently made. Find what specifically is wrong.

"I loop over the array once with a fixed accumulator, so my space is

O (n)

because I touch

n

elements."

Touching

n

elements is time, not space. The accumulator is a single scalar, so auxiliary space is

O (1)

; reading elements does not allocate new memory.

"My function builds a new list of size

n

, but I return it, so it doesn't count toward space."

Returning it does not delete it — the caller now holds it. That new

n

-sized list is auxiliary space you allocated:

O (n)

"Recursion is free memory-wise because the compiler cleans up each frame instantly."

Frames are cleaned up only after they return; while calls are still pending they all sit on the stack simultaneously. Peak depth × frame size is real auxiliary space.

"Storing all

2^{n}

subsets of an

n

-set is

O (2^{n})

space."

Each subset can hold up to

n

elements, so the true footprint is

O (2^{n} \cdot n)

— the count of subsets times their size. Dropping the

n

factor understates it.

"I use a fixed 26-length array to count letters, and strings can be huge, so it's

O (n)

26 is a constant independent of the string length

n

, so the frequency array is

O (1)

auxiliary. Input size never entered the array's size.

"Quick Sort is in-place, so its auxiliary space is

O (1)

Partitioning is in-place, but the recursion stack still costs

O (lo g n)

when balanced (and

O (n)

worst case). The stack is auxiliary space even without extra arrays.

"Tail-recursive or not, recursion depth

n

always means

O (n)

auxiliary in every language."

In languages that perform tail-call optimization, a tail recursion can reuse one frame, giving

O (1)

. Depth-

n

auxiliary assumes no such optimization (as in CPython).

Why questions

Explain the mechanism, not just the label.

Why do we usually compare algorithms by auxiliary space rather than total?

The caller fixes the input size, so the algorithm only controls its scratch memory. Auxiliary space measures the cleverness we can actually influence.

Why does recursion depth, not the number of recursive calls, determine stack space?

Only the calls along the current active path are alive at once; finished calls have popped off. Peak simultaneous frames equals the deepest path, i.e. the depth.

Why is

O (n) + O (n) = O (n)

and not

O (2 n)

when we add input and equal-sized auxiliary?

Big-O ignores constant multiples, so

2 n

collapses to

n

. Both terms grow at the same linear rate, and their sum is still linear.

Why can total space equal auxiliary space for some algorithms?

When the input is

O (1)

(like a single number), the input contributes nothing asymptotically, so total is dominated by whatever scratch you allocate.

Why does an iterative version of a recursive sum use less space than the recursive one?

The loop keeps one running accumulator with no growing stack, giving

O (1)

; the recursion stacks

n

frames, giving

O (n)

. Same time, different peak memory.

Why do we count peak simultaneous usage instead of the total memory ever allocated?

Memory that was freed before a later allocation can be reused, so it never coexists. Space complexity is the maximum held at one instant, not a lifetime sum.

Edge cases

Boundary and degenerate inputs — the cases that break naive rules.

What is the auxiliary space when the input is empty (

n = 0

Still the constant baseline of whatever fixed scratch the function declares, i.e.

O (1)

; asymptotic notation describes growth, so a single empty-case cost is treated as constant.

Quick Sort's auxiliary space in the worst case (already-sorted input, poor pivot) — what happens to the stack?

The recursion becomes unbalanced, peeling one element at a time, so depth reaches

n

and auxiliary space degrades to

O (n)

from the

O (lo g n)

average.

If a function allocates an

n \times n

table, what is its auxiliary space, and does it depend on the input being 1D or 2D?

It is

O (n^{2})

regardless of input shape — the scratch you create is what counts, and an

n \times n

grid holds

n^{2}

cells. The input's dimensionality is irrelevant to your allocation.

Does storing input in a data structure the caller did not give you (e.g. copying it into a hash set) count as auxiliary or input space?

Auxiliary — you allocated that copy yourself. Only the original data handed in by the caller is input space.

For a purely iterative algorithm that mutates the given array and holds a fixed set of indices, what are auxiliary and total space?

Auxiliary is

O (1)

(constant index count, no new arrays); total is

O (n)

because the input array itself must be held.

If two recursive branches run one after another (not nested), how deep does the stack get?

The peak is the depth of the deeper single branch, not their sum — the first branch fully returns and pops before the second starts, so its frames free up first.

Connections

Parent: Auxiliary vs Total — the definitions these traps test.
Recursion and the call stack — the mechanism behind the depth traps.
Merge Sort / Quick Sort — the classic space trade-off items.
In-place algorithms — the " $O (1)$ auxiliary, not zero total" trap.
Time complexity — Big-O notation / Asymptotic notation — Big-O, Big-Omega, Big-Theta — why $O (2^{n})$ time is not $O (2^{n})$ space.