Why does a recursion branching 4 ways at each of L positions cost 4^L, not 4L?
answer
- do the choices replace or stack?
- count the calls one level at a time
- how many calls sit at depth d?
- each branch reopens every choice below it
- geometric sum, last level dominates
basics
~20 sEach call spawns 4 children, so counts multiply level by level instead of adding. Depth d holds 4^d live calls, and L levels of multiplying give 4^L complete patterns. Branching compounds; it does not accumulate.
solid answer
~50 sBecause the branches multiply rather than add. The 4 symbols tried at position 1 each open a fresh 4 choices at position 2, so the number of calls at depth `d` is 4^d, and after `L` positions there are 4^L complete patterns. `4L` would be the count if the loop of 4 ran once, top to bottom; instead every one of those 4 branches re-runs the entire loop beneath it. Summing the whole call tree gives 1 + 4 + 16 + ... + 4^L = (4^(L+1) - 1)/3, which is Θ(4^L) — a geometric series is within a constant factor of its largest term, so the deepest level dominates. The general rule: branching factor `b` and depth `d` give Θ(b^d) calls, and total time is that count times the work each call does outside its own recursion.
code
pseudocode · 11 linesSYMBOLS = [a, b, c, d] // 4 choices per position
explore(prefix, depth):
if depth == L:
record(prefix) // one complete pattern
return
for i in 0..3:
explore(prefix + SYMBOLS[i], depth + 1)
...
explore(empty, 0)go deeper
Recall the rule: branching factor raised to the depth, not multiplied by it. Be able to write out the per-level counts 1, 4, 16, 64 and say why they multiply.
Explain why the geometric sum is dominated by its deepest level, and separate the two counts cleanly: branching sets time, depth sets stack space.
Show the estimate happening before the code: quote b^d for the real input size, add per-leaf work, and say at which length the approach stops being viable.
Own the framing that an exponent in the input is a design constraint, not a tuning problem. Argue when to cap the input size or change the formulation instead of optimising constants.
## The shape of the question A recursion that enumerates something usually has two numbers attached to it: how many recursive calls one invocation makes (the **branching factor**, `b`) and how many levels deep the calls go before hitting a base case (the **depth**, `d`). The single most common mistake when first analyzing such code is to combine those two numbers with multiplication of the wrong kind — to say "4 branches, L levels, so 4L calls". The correct combination is `b^d`, and the difference is not cosmetic: for `b = 4`, `L = 10`, `4L` is 40 and `4^L` is 1,048,576. ## Counting level by level The cleanest way to see it is to count calls one level at a time rather than trying to reason about the tree as a whole. - Level 0: 1 call (the initial one). - Level 1: that call makes 4 calls. Total at this level: 4. - Level 2: **each** of those 4 makes 4 more. Total: 16. - Level d: 4^d. The multiplication happens because the 4 choices at one position are not shared across branches — every branch re-opens the full menu below itself. A loop of 4 that runs once contributes 4; a loop of 4 that is re-entered inside each of its own iterations' subtrees contributes 4 raised to the number of times you nest it. Summing all levels: 1 + 4 + 4^2 + ... + 4^L = (4^(L+1) - 1) / 3 ≈ (4/3) · 4^L So the total node count is Θ(4^L), and — worth internalising — roughly **three quarters of all calls sit at the deepest level alone**. That is the general behaviour of geometric growth: when `b > 1`, the last level outweighs everything above it combined, so the leaf count sets the order of the whole tree. (For `b = 2` the last level is about half; for `b = 4`, three quarters; as `b` grows the leaves dominate ever more completely.) This is why the shorthand "cost = number of leaves" is usually safe for branching recursion, even though it technically ignores the interior calls. ## From call count to time `b^d` counts **calls**, not seconds. To get time you multiply by the work each call performs on its own, excluding the recursive calls it delegates: time = (number of calls) × (work per call) If every call does O(1) bookkeeping and the base case just increments a counter, time is Θ(4^L). If instead each of the 4^L completed patterns is copied out or written somewhere — L symbols each — the leaf work alone is Θ(L · 4^L), and that is the honest bound. Candidates routinely quote `4^L` for code that actually pays `L · 4^L` because they forgot the per-leaf output cost. Space is a separate count and it is much smaller: only one root-to-current path is live at any instant, so the call stack holds at most `L + 1` frames. Depth drives **space**; branching drives **time**. Conflating the two in either direction is the second classic error — the tree has a million nodes but never a million frames at once. ## Non-uniform branching Real enumeration rarely branches a fixed `b` all the way down. Two refinements matter: 1. **The branching factor may shrink with depth.** If each level removes one option from the menu, the counts are n, then n-1, then n-2 … and the product is n! rather than n^n. Same counting method, different product. 2. **Pruning cuts subtrees, not levels.** If a validity check kills a branch at depth 3, everything beneath it — a whole `4^(L-3)` subtree — disappears with it. That is why pruning early is worth so much more than pruning late, and also why `b^d` is an **upper** bound on pruned searches: big-O is a ceiling, and a heavily-pruned enumeration may never come close to it on real inputs. ## The estimate to do before writing code The practical use of `b^d` is to run the arithmetic *before* implementing. Length-6 patterns over 4 symbols: 4^6 = 4,096 — trivial. Length-12: 4^12 ≈ 1.7 × 10^7 — a second or so. Length-20: 4^20 ≈ 1.1 × 10^12 — not happening. The exponent is the lever; adding one position multiplies the cost by 4, while adding one symbol to the alphabet multiplies it by (5/4)^L. Knowing which knob is which is the whole point of writing down `b^d` in the first place.
- A knight-move recursion branches up to 8 ways; does depth k mean 8^k distinct board positions?No. It means up to 8^k distinct move *sequences*, but those sequences land on repeated squares — a board has a fixed number of squares, so the set of positions reachable in k moves is bounded by the board size, not by 8^k. Path count and state count are different quantities, and the gap between them is exactly what caching results per (square, moves-used) exploits. Confusing the two is what makes people think small board searches are hopeless.
- If each completed pattern is copied out at the leaf, what happens to the bound?Copying an L-symbol pattern costs O(L) and there are 4^L leaves, so output work alone is Θ(L · 4^L), and that becomes the total. The interior calls contribute O(1) each and stay inside Θ(4^L), so they don't change the dominant term. The habit worth keeping: b^d counts calls; multiply by per-call work to get time.
- Does the recursion need 4^L memory to hold all those calls?No. Only one root-to-current path is live at any moment, so the call stack holds at most L + 1 frames — O(L) space. The 4^L figure counts calls made over the whole run, not calls alive simultaneously. Memory only becomes 4^L-sized if you deliberately store every completed pattern rather than consuming each one as it is produced.
Four doors in a corridor, and behind each door another corridor with four doors. Walking one corridor is 4 doors; the building has 4^L rooms at the bottom.
saying these in an interview costs you the question
- Says 4 branches over L levels means 4L calls
- Uses recursion depth alone as the total cost
- Assumes anything that recurses n deep is O(n)
- Quotes the call count as time while ignoring per-call work
- Claims the call stack must hold all 4^L calls at once