Why is a function making two recursive calls on n-1 exponential rather than O(n^2)?

## The claim being corrected "It makes two recursive calls, so it does twice the work at each of n levels — that's O(n^2)" is one of the most common wrong answers in the whole subject. It survives because it sounds like arithmetic and because nobody who says it has drawn the tree. Drawing it takes fifteen seconds and settles the question. ## Counting level by level Take the fragment where each invocation makes two calls on `n-1` and does constant work of its own. Label the levels from the root: | level | nodes on that level | |---|---| | 0 | 1 | | 1 | 2 | | 2 | 4 | | 3 | 8 | | k | 2^k | The rule that produces the table is the only thing you need: *every node on a level contributes two nodes to the next level*, so the width is multiplied by two per level, not increased by two. The argument drops by one per level, so the tree bottoms out after about n levels. Adding the levels up (1 + 2 + 4 + ... + 2^(n-1)) gives about 2^n nodes in total — and note that the last level alone holds more nodes than every level above it combined. The tree's cost is dominated by its leaves. ## Where the n^2 intuition comes from, and why it is wrong The `n^2` answer is really the answer to a different shape: **n levels, each costing n**, which is what nested loops look like. It is additive down the levels — level k costs n regardless of k. A branching recursion is not that. Here level k costs 2^k, and the per-level cost grows as you descend. Whenever the per-level cost *grows multiplicatively* with depth, the total is exponential in the depth. The useful mental separation is between **branching factor** (how many children per node — how fast the tree gets wider) and **argument shrinkage** (how fast each call gets smaller — how deep the tree gets). Cost is roughly branching-factor-per-level compounded across the depth. Two calls with a shrink of 1 is the worst combination: maximum depth, and doubling all the way down. ## Same branching, different shapes Three recursions with identical-looking code and wildly different trees: - **One call on `n-1`.** No branching at all; the tree is a chain of about n nodes. Linear. - **Two calls on `n/2`.** Branching doubles the width, but halving the argument means only about log n levels, so the last level has about n nodes and the whole tree about 2n. Linear-ish, not exponential — the branching is paid for by how fast the problem shrinks. - **Two calls on `n-1`.** Doubling for n levels: about 2^n nodes. Exponential. The lesson a strong candidate states explicitly: *branching alone does not make a recursion exponential; branching that outpaces the shrinkage does.* ## Being precise about the exponent Two cautions that separate a careful answer from a slogan. First, `2^n` is exact only when both children recurse on the same argument, as in the fragment above. When the two branches shrink by different amounts — say `n-1` and `n-2`, as in the naive Fibonacci recursion — the tree is lopsided: the shallower branch bottoms out earlier and carries a smaller subtree. Its node count grows like roughly 1.618 to the n, comfortably under 2^n. Saying "the naive Fibonacci recursion makes exactly 2^n calls" is wrong; saying it is O(2^n) is correct but not tight. Second, remember which way a big-O claim points. It is an **upper bound**. Calling something O(2^n) says the node count never exceeds a constant times 2^n; it does not promise the tree is ever that full, and it does not tell you anything about small n, where a tree with 31 nodes is simply not a problem. Interviewers do listen for this: a candidate who claims the bound is achieved, or who panics about exponential growth at n = 5, has the direction of the claim confused. ## What to say at the whiteboard Draw three levels, write 1, 2, 4 beside them, say "each level multiplies by two and there are about n of them", then write 2^n. If asked whether it is tight, check whether both branches shrink by the same amount before you commit.