Exercises — Space complexity — auxiliary vs total

WHAT we count: the number of memory cells the function holds at peak. The cells: 7 scalar integers. That is a fixed number — it does not grow when $n$ (the input length) grows. WHY $O(1)$: Big-O throws away constant factors. "7 cells always" behaves like "1 cell always" as $n\to \infty$. Both are flat lines. Answer: $O(1)$.

Auxiliary: you allocated a list whose length is proportional to $n$ ⇒ one cell per element ⇒ $O(n)$. Total: input list $O(n)$ plus the copy $O(n)$. Adding, $O(n)+O(n)=O(2n)=O(n)$ (constants drop). Answer: auxiliary $O(n)$, total $O(n)$.

Count the cells: $n$ rows, each holding $n$ numbers ⇒ $n\times n=n^2$ cells alive at once. WHY $O(n^2)$: the raw count is $n^2$ (there is no constant multiplier to drop here — one cell per grid square). Big-O keeps the dominant growing term, and $n^2$ grows faster than any lower power of $n$, so the answer is $O(n^2)$. Had we allocated, say, $3n^2$ cells, Big-O would still drop the constant $3$ and report $O(n^2)$ — the same constant-dropping rule as Exercise 1.1. Answer: $O(n^2)$.

Worst case is "all elements distinct." Then seen ends up holding all $n$ elements, and out holds all $n$ too. Peak cells: $O(n)+O(n)=O(n)$. Answer: $O(n)$ auxiliary. (Input is also $O(n)$, so total is $O(n)$ as well.)

The tempting answer: "there's an array, so $O(n)$." The real count: the array freq always has exactly 26 slots, no matter how long the string is. 26 does not grow with $n$. WHY $O(1)$: a fixed-size container is a constant number of cells, so it is $O(1)$ — the same reasoning as 7 scalars in Exercise 1.1. Answer: $O(1)$ auxiliary.

Count what out holds at peak: the double loop runs $n\times n=n^2$ times, and each iteration appends one number. So out grows to $n^2$ cells. Careful: the time is $O(n^2)$ and the space is also $O(n^2)$ here — but only because we store every product. If we merely summed them, space would be $O(1)$. Answer: $O(n^2)$ auxiliary.

How deep does it go? Each call increases i by 1 until i == n. So the chain is $n$ calls long before the first return 0 fires. Peak frames alive: $n$ frames stacked at once ⇒ $O(n)$ stack. Answer: $O(n)$ auxiliary — even though the function returns a single number and declares almost nothing.

The trap: the time is $O(2^n)$ (exponentially many calls), so people write $O(2^n)$ for space too. The truth: space = peak simultaneous frames, not total calls. The calls happen mostly one-after-another and return before their siblings start. At any instant, the deepest live chain is fib(n) → fib(n-1) → fib(n-2) → ... → fib(1), which is depth $n$. Answer: $O(n)$ auxiliary. (Time $O(2^n)$, space $O(n)$ — different resources, different answers.)

How deep before hitting size 1? Starting at $n$ and halving: $n\to n/2\to n/4\to \cdots \to 1$. The number of halvings to reach 1 is the exponent $k$ with $2^k=n$, i.e. $k={\log }_{2}n$. WHY logarithm and not $n$: we don't subtract 1 each time (that gives depth $n$); we divide by 2, and repeated division is measured by $\log$. That is precisely why balanced divide-and-conquer stacks are so shallow. Answer: $O(\log n)$ auxiliary (stack), balanced case.

(a) Temp array: merging needs a scratch buffer as big as the part being merged; at the top level that is $n$ ⇒ $O(n)$. (b) Recursion stack: halving each level ⇒ depth $\log n$ ⇒ $O(\log n)$ (each frame holds a few scalars). (c) Combined: peak auxiliary is the sum, $O(n)+O(\log n)$. Since $n$ dominates $\log n$ for large $n$, this simplifies to $O(n)$. Answer: (a) $O(n)$, (b) $O(\log n)$, (c) $O(n)$.

No temp array ⇒ the only auxiliary is the recursion stack. (a) Balanced: each partition splits roughly in half ⇒ depth $\log n$ ⇒ $O(\log n)$. (b) Worst case: a bad pivot peels off just one element per call, so the chain is n → n-1 → n-2 → ... → 1, depth $n$ ⇒ $O(n)$ stack. Answer: (a) $O(\log n)$, (b) $O(n)$. WHY the gap: balanced recursion divides (log depth); degenerate recursion subtracts one (linear depth) — exactly the contrast from Exercises 3.1 and 3.3.

A's cells: $\approx n=1,048,576$. B's cells: $\approx {\log }_2(1,048,576)$. Since $2^{20}=1,048,576$, we get ${\log }_{2}n=20$ exactly. Ratio: $\frac{1,048,576}{20}=52,428.8$. Answer: about 52,000× more auxiliary memory for A. Same time class, wildly different memory — the whole reason Quick Sort is often preferred over Merge Sort when memory is tight.

How many subsets? Each of the $n$ elements is either in or out — $2$ choices each — giving $2\times 2\times \cdots =2^n$ subsets. How big is each? A subset can be up to $n$ elements long. Total stored cells: (number of subsets) × (size each) $=2^n\cdot n$. Answer: $O(2^n\cdot n)$ auxiliary. Contrast: if we only processed each subset one at a time and threw it away, auxiliary would collapse to the recursion depth $O(n)$ — the storing is what makes it exponential.

Balanced: the longest root-to-leaf path is the tree's height. A balanced tree of $n$ nodes has height $\approx {\log }_{2}n$ (each level doubles the node count). Only one such path is alive at a time (siblings finish first). Answer (balanced): $O(\log n)$. Skewed (chain): height equals $n$ (a straight line of nodes) ⇒ $O(n)$. WHY: stack depth = tree height, and height ranges from $\log n$ (balanced) to $n$ (chain) — the same "divide vs subtract-one" story as Quick Sort in Exercise 4.2.

Design A (recursive): recursion goes as deep as the list is long — $n$ frames alive at the peak ⇒ $O(n)$ auxiliary stack. Design B (iterative, 3 pointers): exactly three scalar pointers, no matter how long the list ⇒ $O(1)$ auxiliary. Better: Design B, because it turns hidden $O(n)$ stack cost into $O(1)$ constant memory — an in-place rewrite. The lesson: recursion's elegance can secretly cost $O(n)$ space (Exercise 3.1); an iterative accumulator often reclaims it.

Set up: the algorithm holds $n^2$ cells, and we want that to equal one billion, so $n^2=10^9$. Solve: $n=\sqrt{10^9}$. Split the exponent: $10^9=10^8\cdot 10$, and $\sqrt{10^8}=10^4$, so $n=10^4\cdot \sqrt{10}\approx 10^4\cdot 3.162=31,623$. Check: $31,623^2\approx 1.0\times 10^9$ ✓. Answer: $n\approx 31,623$. Concluding remark: a quadratic table blows past a billion cells at only about thirty thousand elements — a tiny input by modern standards. That is exactly why an $O(n^2)$ space algorithm is dangerous long before the machine feels slow: it runs out of memory well before it runs out of time, which is a concrete reason to prefer linear or logarithmic auxiliary designs whenever you can.