Recursion Time Complexity: The Tree, the Recurrence, and the Master Theorem

Most engineers can analyze a loop in five seconds. Count iterations, multiply by work per iteration, done. But the moment a function calls itself, something breaks. Specifically, your mental model of what "counting operations" means falls apart completely, and you end up staring at a call stack 40 frames deep wondering how you got here.

Two tools make recursion time complexity mechanical: the recursion tree and the recurrence relation. Add the Master Theorem and almost every recursive function you encounter in interviews becomes straightforward to analyze.

Gru plans to analyze recursive time complexity but gives up

Yep. Still the most accurate diagram of the learning process.

What Does Recursion Time Complexity Actually Count?

For a loop, you count iterations. For recursion, you count nodes in the call tree, then multiply by the work each node does.

Every recursive function call creates one node in that tree. The root is the original call. Its children are the recursive calls it spawns. The leaves are the base cases. The total work the function does equals the sum of work across every node.

That sum is what you are computing when you analyze a recursive algorithm.

Draw the Recursion Tree First

Factorial: A Chain, Not a Tree

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

One recursive call, size n-1, plus O(1) work (one multiplication). Draw it:

factorial(5)
  └── factorial(4)
        └── factorial(3)
              └── factorial(2)
                    └── factorial(1)   ← base case

Factorial call chain: n boxes stacked vertically, each calling the next smaller, base case highlighted at the bottom

A chain, not a tree. n frames, O(1) each.

Exactly n nodes. O(1) work per node. Total time: O(n).

This is the simplest case: one call, constant work, linear total. It's almost insulting how easy it is. Don't worry, that feeling won't last.

Merge Sort: Where the Tree Branches

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)   # O(n) work here

Two recursive calls, each on a half-size array, plus O(n) work per call to merge. Now the tree fans out:

Level 0:          [n]                      → n work
Level 1:      [n/2]  [n/2]               → n/2 + n/2 = n work
Level 2:  [n/4][n/4][n/4][n/4]           → 4 × (n/4) = n work
...
Level k:  2^k nodes, each size n/2^k     → 2^k × (n/2^k) = n work

Merge sort recursion tree: four levels, each level's work labeled on the right summing to n, with O(n log n) total shown at the bottom

Every level pays n. The bill just arrives log n times.

Every level contributes exactly n total work. If this seems suspiciously clean, that's because it is. Divide-and-conquer is basically engineered to produce this property. How many levels? The input halves at each level, so after log₂ n halvings, each subproblem has size 1. That gives log n + 1 levels.

Total: n work × log n levels = O(n log n).

This is the recursion tree method in full. Build the tree, find the work per level, count the levels, sum. It sounds like homework. It is homework. It works every time.

From Picture to Formula: Meet the Recurrence

A recursion tree is a picture. A recurrence relation is the same information written as an equation. You need both because the tree gives intuition and the algebra gives precision.

To write a recurrence for any recursive function, answer three questions:

How many recursive calls does one invocation make? Call this a.
What fraction of the current input size does each recursive call get? Call this 1/b.
How much work does one call do outside of recursion? Call this f(n).

Then write: T(n) = a · T(n/b) + f(n).

For factorial: T(n) = T(n-1) + 1 (one call, size n-1, constant outside work). For merge sort: T(n) = 2T(n/2) + n (two calls, half size, linear merge work).

You can solve simple recurrences by substitution. Factorial:

T(n) = T(n-1) + 1
     = T(n-2) + 1 + 1
     = T(n-3) + 3
     ...
     = T(1) + (n-1)
     = O(n)

For divide-and-conquer recurrences, substitution gets tedious. There is a shortcut.

The Master Theorem: One Comparison, One Answer

The Master Theorem is a pattern-matching formula for recurrences of the form T(n) = aT(n/b) + n^d. It compares how fast the number of subproblems grows (captured by a) against how fast each subproblem shrinks (captured by b^d). That comparison tells you which part of the tree dominates.

Three recursion tree shapes side by side: leaf-heavy with gold leaves, balanced with equal blue levels, and root-heavy with a dominant purple root

Left: leaves eat everything. Middle: everybody pays equally. Right: the root is the only one doing real work.

Condition	Winner	Result
`a > b^d`	Leaves	`Θ(n^(log_b a))`
`a = b^d`	Even	`Θ(n^d · log n)`
`a < b^d`	Root	`Θ(n^d)`

Case 1 (leaf-heavy): Each recursive call spawns so many children that work explodes toward the leaves. The leaf level dominates. Total work scales with the number of leaves, which is a^(log_b n) = n^(log_b a).

Case 2 (balanced): Every level in the tree contributes the same amount of work. You pay n^d work at each of log n levels, so multiply.

Case 3 (root-heavy): Work shrinks as you go deeper. The root's single call does more than all the leaves combined. A geometric series tells you the total is dominated by the first term.

Three Algorithms, Three Cases

Merge sort: T(n) = 2T(n/2) + n. Here a = 2, b = 2, d = 1. Compare: a = 2, b^d = 2¹ = 2. They match. Case 2: Θ(n log n). Matches the tree.

Binary search: T(n) = T(n/2) + 1. Here a = 1, b = 2, d = 0. Compare: a = 1, b^d = 2⁰ = 1. Match again. Case 2: Θ(log n).

A hypothetical: T(n) = 3T(n/2) + n. Here a = 3, b = 2, d = 1. Compare: a = 3, b^d = 2. Since a > b^d, Case 1: Θ(n^(log₂ 3)) ≈ Θ(n^1.585).

One limitation: the Master Theorem only applies when the subproblem size shrinks by a fixed factor, giving n/b style recurrences. Factorial gives T(n) = T(n-1) + 1, which subtracts a constant. That falls outside the theorem's scope. Use substitution for those. This is not a technicality you can wave away; the theorem genuinely does not apply to linear recurrences.

Your Call Stack Is Keeping a Tab

Time complexity is about how much work happens. Space complexity is about how much memory the call stack holds at any given moment.

When a function calls itself, the current frame has to stay alive. It cannot return yet. Its local variables, its parameters, and its return address all sit in memory, waiting. Each nested call pushes a new frame on top.

Space complexity equals the maximum number of frames alive simultaneously, times the space each frame uses.

For most functions, each frame uses O(1) space (a few variables). So space complexity reduces to: what is the maximum depth of the call stack?

Call stack for factorial(4): four stacked frames labeled factorial(1) through factorial(4), right brace showing max depth = n

Four frames. Each one waiting politely for the one above it to finish.

Factorial: The call chain goes n frames deep before hitting the base case. Peak stack size: n frames. Space: O(n). Get this wrong and you get a stack overflow, which is a real error and not a website.

Binary search (recursive): The array halves at each call. Depth is log n. Space: O(log n).

Merge sort: Depth is log n (the input halves at each level). But each merge step may allocate temporary arrays. Whether space is O(n) or O(n log n) depends on the implementation. A simple implementation that allocates a new list in each merge call pays O(n) at every level, giving O(n log n) space. Pre-allocate a single scratch buffer and it stays O(n).

Fibonacci: The Function That Looks Fine Until It Destroys You

No function shows the gap between time and space more clearly than Fibonacci.

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

The recurrence is T(n) = T(n-1) + T(n-2) + 1. This does not fit the Master Theorem form because the two subproblems are not the same size. Solve it by recognizing that T(n-1) ≥ T(n-2), which gives a lower bound:

T(n) ≥ T(n-2) + T(n-2) = 2T(n-2)
T(n) ≥ 2·2T(n-4) = 4T(n-4)
...
T(n) ≥ 2^(n/2) · T(0)
T(n) = Ω(2^(n/2))

The tighter analysis uses the characteristic equation x² = x + 1, whose positive root is the golden ratio φ = (1+√5)/2 ≈ 1.618. The Fibonacci sequence itself grows as Θ(φⁿ), and the number of function calls tracks Fibonacci numbers exactly. Time complexity: Θ(φⁿ) ≈ O(1.618ⁿ).

In practical terms: exponential. If you call fib(50) without memoization during an interview, the interviewer will watch it hang, and you will both sit there in silence for a while. Try fib(35) at home sometime, just to feel it.

Fibonacci recursion tree for n=5, gold path highlighting the deepest left branch showing O(n) stack depth, rest of tree in blue showing the exponential total

Gold = the active call stack path. Blue = the rest of the tree. Time is exponential. Space is just that one gold path.

Now for space: look at the tree and pick the deepest path. Starting from fib(n), the deepest branch goes fib(n-1), fib(n-2), ..., fib(1). That path has length n. While fib(n) is calling down the left branch, the right branch has not started yet. The call stack only holds the current active path.

Space complexity: O(n). Not O(2ⁿ). Not O(φⁿ). Linear.

The tree has exponentially many nodes in total, but only n of them are alive on the call stack at once. The two siblings at each level take turns. The tree's width is irrelevant to space. The call stack does not simulate all branches simultaneously; it goes one path at a time, completes it, backs up, and goes the next.

This is also why memoization works so well: cache fib(k) the first time and you never descend the right branch again. Time collapses from Θ(φⁿ) to O(n), while space stays O(n). That is exactly what dynamic programming does.

Which Tool to Reach For

Recursion tree: always. Draw it when anything is unclear. It cannot lie.
Master Theorem: your first move for divide-and-conquer recurrences. One comparison, done.
Substitution: for linear recurrences (T(n-1), T(n-2) forms) that do not fit the Master Theorem.
For space: ignore time, find the deepest path, count frames. That's it.

When you explain this in a mock interview, the interviewer wants to hear you narrate the tree before you write the formula. You can practice exactly that kind of out-loud complexity reasoning at SpaceComplexity, which runs voice-based mock interviews with rubric feedback on your analysis.

Recap

The recursion tree method: draw the call tree, sum the work at each level, count the levels.
Merge sort's O(n log n) comes from n total work per level times log n levels, each level balanced.
Recurrences let you write the same logic as algebra: T(n) = a·T(n/b) + f(n).
The Master Theorem solves T(n) = aT(n/b) + n^d in one step: compare a vs b^d.
Space complexity equals max recursion depth times space per frame. Tree width is irrelevant.
Fibonacci: O(φⁿ) time, O(n) space. The call stack only holds one root-to-leaf path at a time.