Space complexity — auxiliary vs total — Coding notes

HOW to count space — first principles

We count every "memory cell" the program is alive-and-holding at the same time (peak simultaneous usage), then keep the dominant term.

Rules of thumb (derived, not memorized):

A fixed number of scalar variables ⇒ $O(1)$ (constant — doesn't grow with $n$ ).
An array/list of length proportional to $n$ ⇒ $O(n)$ .
A 2D table of size $n \times n$ ⇒ $O(n^2)$ .
Recursion costs stack space = (max depth of recursion) × (space per frame). This is the most-missed source of space!

Figure — Space complexity — auxiliary vs total

Worked Examples

Worked example Example 1 — In-place array reversal

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

Auxiliary: only i, j (a constant count) ⇒ $O(1)$ $O (1)$ .
- Why this step? Variable count doesn't grow with $n$ ; the swap reuses the same array.
Total: input array $O(n)$ $O (n)$ + aux $O(1)$ $O (1)$ ⇒ $O(n)$ $O (n)$ .
- Why this step? Total must include the $n$ -sized input we're holding.

Worked example Example 2 — Building a copy

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

Auxiliary: new list out of size $n$ $n$ ⇒ $O(n)$ $O (n)$ .
- Why? We created that array; it's scratch we control.
Total: input $O(n)$ $O (n)$ + aux $O(n)$ $O (n)$ = $O(n)$ $O (n)$ .
- Why? $O(n)+O(n)=O(2n)=O(n)$ ; constants drop.

Worked example Example 3 — Recursive sum (the sneaky one)

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

Auxiliary: recursion goes $n$ $n$ frames deep before any returns ⇒ $O(n)$ $O (n)$ stack.
- Why? All $n$ frames coexist at peak.
Iterative version (for loop with one accumulator) would be $O(1)$ $O (1)$ auxiliary.
- Why? No stack growth; one running total.

Worked example Example 4 — Merge Sort vs Quick Sort

Algorithm	Auxiliary space	Why
Merge Sort	$O(n)$	needs a temp array to merge halves
Quick Sort	$O(\log n)$ avg	only recursion stack (in-place partition), depth $\approx \log n$ when balanced

Why this matters: Both are $O(n\log n)$ time, but Quick Sort wins on auxiliary space.

Active Recall — Flashcards

#flashcards/coding

What is auxiliary space?

Extra memory an algorithm allocates beyond the input (temp vars, helper arrays, recursion stack).

What is total space?

Input space + auxiliary space.

Why do we usually report auxiliary space when comparing algorithms?

Because the algorithm controls only the scratch memory; input size is fixed by the caller.

What hidden cost does recursion add to space?

The call stack — depth × frame size; max simultaneous frames count as auxiliary space.

Auxiliary space of in-place array reversal?

O(1).

Auxiliary space of naive recursive Fibonacci?

O(n) (max stack depth), NOT O(2^n) which is its time.

Merge sort vs quick sort auxiliary space?

Merge O(n) (temp array); Quick O(log n) average (recursion stack).

Total space formula?

Total = S_input + S_aux.

Why is storing all subsets O(2^n · n) space?

There are 2^n subsets, each up to n elements long.

A function with 5 scalar locals and no arrays — auxiliary space?

O(1), constant count independent of n.

Recall Feynman: explain to a 12-year-old

Imagine you're given a big box of LEGO (that's the input). To build something, you sometimes grab an empty tray to sort pieces on the side — that tray is your auxiliary space, the extra stuff you brought out. Total space is the box plus the tray together. A smart builder uses a tiny tray (less auxiliary). And careful! If you keep starting new little side-projects one inside another (recursion), each one needs its own little tray, and they all sit on the table at once — that's a sneaky pile of trays you forgot to count.

Connections

Time complexity — Big-O notation — same asymptotic machinery, different resource.
Recursion and the call stack — source of hidden auxiliary space.
Merge Sort / Quick Sort — classic space trade-off.
In-place algorithms — algorithms designed for $O(1)$ auxiliary.
Asymptotic notation — Big-O, Big-Omega, Big-Theta — how we drop constants.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, jab bhi koi algorithm chalta hai, usko memory chahiye hoti hai. Ye memory do parts mein baat lo: ek to input space — jo data tumhe diya gaya hai (jaise ek array of size n), aur dusra auxiliary space — jo extra scratch tum khud banate ho (temp variables, helper arrays, ya recursion ka stack). Total space = input + auxiliary. Bas itni si baat hai, par interview mein log galti yahin karte hain ki kaun sa poocha gaya hai.

Jab hum compare karte hain ki "konsa algorithm zyada smart hai memory bachane mein", tab hum mostly auxiliary dekhte hain — kyunki input ki size to caller ne fix kar di, usme tumhara koi control nahi. Lekin agar real machine pe footprint dekhna ho, tab total chahiye.

Sabse sneaky cheez hai recursion. Log sochte hain "function to bas ek number return karta hai, koi extra memory nahi". Galat! Har pending recursive call apna ek stack frame rakhti hai jo return hone tak zinda rehta hai. Agar depth n hai, to n frames ek saath table pe pade hain — yani $O(n)$ auxiliary space. Isiliye recursive sum $O(n)$ space leta hai, par iterative loop wala sirf $O(1)$ .

Yaad rakhne ka shortcut: "AUX = jo main add karta hoon, TOTAL = jo main hold karta hoon." Aur recursion ke liye — "deep stack matlab chhupi hui space." Bas itna samajh lo to space complexity ke questions clear ho jayenge.

Space complexity — auxiliary vs total

WHAT are we measuring?

HOW to count space — first principles

Worked Examples

Active Recall — Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Complexity Analysis

Connections