Quiz (3)
Quiz: Space Complexity
Questions on auxiliary memory, the call stack, and the traps that catch strong candidates: tail-call space, why the recursion-stack estimate is not the whole story, and what “space” even counts. Recompute before peeking.
1. What does space complexity measure?
Answer: The auxiliary memory used as a function of input size — extra space beyond the input itself, including the recursion call stack.
2. Reversing an array in place by swapping the two ends inward?
Answer: O(1) — only a couple of index/temp variables; no structure that grows with n.
3. A linear recursion that makes n nested calls before any returns?
Answer: O(n) — all n call frames are live on the stack simultaneously until the base case unwinds.
4. Building a hash set of all n elements to detect duplicates?
Answer: O(n) — the set stores up to n entries.
5. Does O(n) time imply O(n) space?
Answer: No. Time and space are independent. Summing an array is O(n) time but O(1) space; a DP table can be O(n) time and O(n) space. Always analyze them separately.
6. Trap: a recursive function that ends in return f(n−1) — is that O(1) space?
Answer: Only if the language guarantees tail-call optimisation (TCO). A tail call (the recursive call is the last action, its result returned directly) can in principle reuse one frame → O(1) stack. But Java, Python, and JavaScript in practice do NOT eliminate tail calls — ES6 mandates proper tail calls on paper, yet V8 (Chrome/Node) and SpiderMonkey (Firefox) never shipped them; only JavaScriptCore (Safari) did — so in those languages it is still O(n) stack and can overflow. Scheme, and most functional compilers, do. Never claim O(1) stack for tail recursion without naming the language's guarantee — otherwise assume O(depth).
7. Merge sort recurses only O(log n) deep. Is its space complexity therefore O(log n)?
Answer: No — O(n). Two things allocate: the recursion stack (O(log n) frames) and the auxiliary buffer the merge step needs to hold up to n elements while combining two sorted halves. Total space is the sum of all simultaneously-live allocations, dominated by the O(n) buffer — so standard array merge sort is O(n) auxiliary space. The trap is counting only the call stack. Contrast in-place quicksort, which allocates no merge buffer: its space is just the recursion stack — O(log n) on balanced partitions (O(n) on worst-case skew). This is the concrete reason quicksort is called “in-place” and array merge sort is not, and why a linked-list or external merge sort is reached for when that buffer is unaffordable.
8. Convention trap: a recursion that returns all 2ⁿ subsets of n items has a recursion depth of only O(n). Is its space O(n)?
Answer: Depends what you count — state it. Auxiliary/working space (the call stack plus the current partial subset) is O(n). But the output you materialise is O(n·2ⁿ) — the results dwarf the stack. By convention “space complexity” usually means auxiliary space, excluding the required output, but you must say which: an interviewer asking “can you do this in O(n) space?” almost always means auxiliary, whereas “how much memory does this use?” includes the output. Naming the convention before answering is the mark of a careful candidate.
Self-check quiz authored for this guide — Grokking Algorithm Complexity & Big-O.
🤖 Don't fully get this? Learn it with Claude
Stuck on Quiz (3)? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.
Build the mental picture, not memorization.
I just read a lesson on **Quiz (3)** (DSA) and want to truly understand it. Explain Quiz (3) from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Socratic — adapts to where you're stuck.
Teach me **Quiz (3)** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Active recall exposes what you missed.
Quiz me on **Quiz (3)** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
Intuition + hook + flashcards for long-term memory.
Help me remember **Quiz (3)** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.