Space complexity — auxiliary vs total — Hinglish notes

3.1.4 · Coding › Complexity Analysis

HUM KYA MEASURE kar rahe hain?

SPACE COUNT kaise karein — first principles

Hum har "memory cell" ko count karte hain jo program ek saath alive-and-holding rakhta hai (peak simultaneous usage), phir dominant term rakhte hain.

Rules of thumb (derived, memorized nahi):

Ek fixed number of scalar variables ⇒ $O (1)$ (constant — $n$ ke saath nahi badhta).
Ek array/list jiska length $n$ ke proportional ho ⇒ $O (n)$ .
Ek 2D table of size $n \times n$ ⇒ $O (n^{2})$ .
Recursion stack space leta hai = (max recursion depth) × (space per frame). Yeh space ka sabse zyada miss hone wala source hai!

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: sirf i, j (ek constant count) ⇒ $O (1)$ .
- Yeh step kyun? Variable count $n$ ke saath nahi badhta; swap same array reuse karta hai.
Total: input array $O (n)$ + aux $O (1)$ ⇒ $O (n)$ .
- Yeh step kyun? Total mein woh $n$ -sized input bhi include hona chahiye jo hum hold kar rahe hain.

Worked example Example 2 — Copy banana

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

Auxiliary: naya list out of size $n$ ⇒ $O (n)$ .
- Kyun? Humne woh array banaya hai; yeh woh scratch hai jo hum control karte hain.
Total: input $O (n)$ + aux $O (n)$ = $O (n)$ .
- Kyun? $O (n) + O (n) = O (2 n) = O (n)$ ; constants drop ho jaate hain.

Worked example Example 3 — Recursive sum (sneaky wala)

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

Auxiliary: recursion koi bhi return hone se pehle $n$ frames deep jaati hai ⇒ $O (n)$ stack.
- Kyun? Sab $n$ frames peak par coexist karte hain.
Iterative version (ek accumulator ke saath for loop) $O (1)$ auxiliary hota.
- Kyun? Koi stack growth nahi; ek running total.

Worked example Example 4 — Merge Sort vs Quick Sort

Algorithm	Auxiliary space	Kyun
Merge Sort	$O (n)$	halves merge karne ke liye ek temp array chahiye
Quick Sort	$O (lo g n)$ avg	sirf recursion stack (in-place partition), depth $\approx lo g n$ jab balanced ho

Yeh kyun matter karta hai: Dono $O (n lo g n)$ time mein hain, lekin Quick Sort auxiliary space mein jeet jaata hai.

Active Recall — Flashcards

#flashcards/coding

What is auxiliary space?

Woh extra memory jo algorithm input se alag allocate karta hai (temp vars, helper arrays, recursion stack).

What is total space?

Input space + auxiliary space.

Why do we usually report auxiliary space when comparing algorithms?

Kyunki algorithm sirf scratch memory control karta hai; input size caller ne fix ki hoti hai.

What hidden cost does recursion add to space?

Call stack — depth × frame size; max simultaneous frames auxiliary space mein count hote hain.

Auxiliary space of in-place array reversal?

O(1).

Auxiliary space of naive recursive Fibonacci?

O(n) (max stack depth), O(2^n) NAHI jo uska time hai.

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?

2^n subsets hote hain, har ek n elements tak lamba hota hai.

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

O(1), constant count jo n se independent hai.

Recall Feynman: ek 12-saal ke bachche ko samjhao

Socho tumhe LEGOs ka ek bada dabba diya gaya hai (yeh input hai). Kuch banana ke liye, tum kabhi kabhi ek khali tray nikalte ho pieces sort karne ke liye — woh tray tumhari auxiliary space hai, woh extra cheez jo tum khud laaye ho. Total space dabba aur tray dono milake hoti hai. Ek smart builder ek chhoti tray use karta hai (kam auxiliary). Aur dhyan do! Agar tum ek ke andar ek nayi chhoti side-projects shuru karte jaate ho (recursion), toh har ek ko apni chhoti tray chahiye, aur woh sab ek saath table par rakhti hain — yeh trayon ka ek sneaky dher hai jise tum count karna bhool gaye.

Connections

Time complexity — Big-O notation — same asymptotic machinery, alag resource.
Recursion and the call stack — hidden auxiliary space ka source.
Merge Sort / Quick Sort — classic space trade-off.
In-place algorithms — $O (1)$ auxiliary ke liye design kiye gaye algorithms.
Asymptotic notation — Big-O, Big-Omega, Big-Theta — constants kaise drop karte hain.