Quiz (4)
Quiz: Recursion & Recurrences
Solve each recurrence to its Big-O. The first five are the canonical shapes; the last three are the ones people get wrong — a tree-shape trap, a branching-factor trap, and the one comparison that replaces memorising them all. Recompute before peeking.
1. T(n) = 2·T(n/2) + O(n) (merge sort)?
Answer: O(n log n) — O(n) work per level across log n levels of halving.
2. T(n) = T(n−1) + O(1) (simple linear recursion)?
Answer: O(n) — n levels deep, O(1) work each.
3. T(n) = 2·T(n−1) + O(1) (naive recursive Fibonacci)?
Answer: O(2ⁿ) — each call spawns two, and depth is n, so the call tree is exponential. The recurrence as written (2·T(n−1)) gives 2ⁿ as a clean upper bound; true Fibonacci is T(n) = T(n−1) + T(n−2) + O(1), whose tight bound is Θ(φⁿ) with φ ≈ 1.618 (the golden ratio) — still exponential, so O(2ⁿ) is correct but loose. Knowing the φⁿ refinement is a real interview differentiator. Memoization collapses it to O(n).
4. T(n) = T(n/2) + O(1) (binary search)?
Answer: O(log n) — one branch, halving each step.
5. What is the space of a depth-d recursion (DFS style)?
Answer: O(d) — only one root-to-leaf path is on the stack at a time, so peak stack depth equals the tree height d, not the total number of calls.
6. For a binary-tree DFS on n nodes, is the stack space O(log n) or O(n)?
Answer: It depends on the tree's shape — O(height). A balanced tree has height ≈ log₂n, so O(log n) stack; a degenerate/skewed tree (every node has one child, i.e. a linked list) has height n, so O(n) stack and a real stack-overflow risk. Never quote O(log n) for tree recursion unless balance is guaranteed. This is also why merge sort's recursion is O(log n) deep (always halved) while naive quicksort on sorted input recurses O(n) deep — the fix is to recurse on the smaller partition first.
7. Solve T(n) = T(n/2) + O(n) — is it O(n log n) like merge sort?
Answer: No — O(n). There is only one recursive call (not two), so the work per level shrinks geometrically: n + n/2 + n/4 + … = 2n = O(n). The trap is pattern-matching to merge sort’s T(n) = 2·T(n/2) + O(n) = O(n log n); the difference is the branching factor. With one branch, the top level’s O(n) dominates the entire sum. By the Master Theorem: a=1, b=2, f(n)=n; compare f(n) to n^(log₂a) = n^(log₂1) = n⁰ = 1 — since f(n)=n grows faster, the root work dominates → Θ(n). (This is the shape of quickselect’s average-case recurrence.)
8. The Master method in one comparison: for T(n) = a·T(n/b) + O(n^d), why do 2T(n/2)+O(n) and 2T(n/2)+O(n²) land on different answers?
Answer: Compare the exponent d against log₂a (how fast work multiplies going down vs. how fast each subproblem shrinks): if d < logₖa → Θ(n^(logₖa)) (leaves dominate); if d = logₖa → Θ(n^d·log n) (every level costs the same); if d > logₖa → Θ(n^d) (root dominates). So 2T(n/2)+O(n): a=2, b=2, d=1, and log₂2 = 1 = d → tie → Θ(n log n) (merge sort). But 2T(n/2)+O(n²): d=2 > log₂2 = 1 → root dominates → Θ(n²) — the single top-level O(n²) swamps everything beneath it. Lesson: don’t memorise five recurrences — internalise this one race between branching (a) and shrink rate (b, d).
Self-check quiz authored for this guide — Grokking Algorithm Complexity & Big-O.
🤖 Don't fully get this? Learn it with Claude
Stuck on Quiz (4)? 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 (4)** (DSA) and want to truly understand it. Explain Quiz (4) 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 (4)** 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 (4)** 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 (4)** 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.