Recursion trees & complexity
In one line
Draw the calls as a tree: total time is the work summed over every node, and extra space is the height of the tree, which is the deepest chain of calls.
What it is
A recursion tree draws each call as a node, with its recursive calls as children. The root is the original call and the leaves are base cases. It turns the vague question 'how slow is this recursion?' into counting: how many nodes are there, and how much work does each do outside its recursive calls?
Two numbers fall out of the tree. Time is the sum of the work at every node. Space is the height of the tree (the stack depth) times the memory per frame, plus any data structures you build. A function with two calls on n - 1 doubles its nodes on every level, while a function with two calls on n / 2 doubles the nodes but halves the size, which gives a completely different result.
Why interviewers ask
Interviewers almost always ask for complexity, and recursive code is where candidates guess most. Being able to say 'two branches, depth n, so about 2^n calls' or 'log n levels with O(n) work each, so O(n log n)' shows real understanding. It also explains why memoization helps and why some recursive solutions time out.
How it works
- 1Write the recurrence: T(n) = (number of calls) x T(smaller size) + (work done in this call). For merge sort, T(n) = 2T(n/2) + O(n).
- 2Draw the first few levels of the tree and note how many nodes each level has and the size of each node's input.
- 3Find the work per level. For merge sort every level splits n items among its nodes, so each level does O(n) work.
- 4Find the number of levels: halving gives about log2(n) levels, subtracting 1 gives n levels.
- 5Multiply or sum: merge sort is O(n) per level x log n levels = O(n log n). If levels grow geometrically, the biggest level dominates.
- 6Space is the depth of the tree, not its size: fib(n) has about 1.6^n calls but only n frames on the stack at once.
Worked example · Counting the calls of naive fib(4)
- fib(4) calls fib(3) and fib(2).
- fib(3) calls fib(2) and fib(1). Each fib(2) calls fib(1) and fib(0).
- Count with calls(n) = 1 + calls(n - 1) + calls(n - 2), where calls(0) = calls(1) = 1.
- calls(2) = 1 + 1 + 1 = 3. calls(3) = 1 + 3 + 1 = 5. calls(4) = 1 + 5 + 3 = 9.
- fib(2) was computed twice and fib(1) three times. The counts keep growing like Fibonacci numbers: calls(10) = 177 and calls(20) = 21,891, which is exponential, roughly 1.6^n.
- The deepest path is fib(4), fib(3), fib(2), fib(1): 4 frames, so the stack space is O(n) even though the time is exponential.
Picture it
A recursion tree is like a company's org chart where each manager hands work to their reports. To know the total effort, add up what every person does. To know how long a message takes to travel from the CEO to the most junior person, look at how many layers deep the chart is. Those are time and space.
Reference code
calls = 0
def fib(n):
# two calls per level: about 1.6^n calls, O(2^n) as a safe bound
global calls
calls += 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
def binary_search(a, target, lo, hi):
# one call on half the range: O(log n) time and O(log n) stack
if lo > hi:
return -1
mid = (lo + hi) // 2
if a[mid] == target:
return mid
if a[mid] < target:
return binary_search(a, target, mid + 1, hi)
return binary_search(a, target, lo, mid - 1)
for n in (4, 10, 20):
calls = 0
fib(n)
print(n, calls) # 4 9, 10 177, 20 21891
print(binary_search([1, 3, 5, 7, 9, 11], 9, 0, 5)) # 4
The counter makes the exponential growth of naive Fibonacci visible: 9, 177 and 21,891 calls for n = 4, 10 and 20. Binary search makes one call on half the range, so its tree is a single path of length about log2(n).
Key patterns
Branching on n - 1
When: Each call makes b calls on n - 1 (naive Fibonacci, subsets, include or exclude)
How: About b^n calls; depth n. With memoization, time becomes number of distinct states times work per state.
Halving with linear combine
When: T(n) = 2T(n/2) + O(n), as in merge sort
How: log n levels, O(n) work each: O(n log n). Stack depth O(log n).
Single branch on half
When: T(n) = T(n/2) + O(1), as in binary search
How: O(log n) time. Quickselect, T(n) = T(n/2) + O(n), is O(n) on average because the work shrinks geometrically.
Master theorem
When: T(n) = aT(n/b) + O(n^d)
How: Compare d with log_b(a): if d is larger, O(n^d); if equal, O(n^d log n); if smaller, O(n^(log_b a)). Example: 8T(n/2) + O(n^2) is O(n^3).
Permutations
When: Building every ordering of n items
How: n! leaves, and copying each result costs O(n), so O(n x n!) total.
Real-world use
Karatsuba multiplication in CPython
CPython multiplies very large integers with Karatsuba's method: three recursive multiplications on half-size numbers instead of four. The recurrence T(n) = 3T(n/2) + O(n) gives about O(n^1.585) instead of O(n^2).
Fast Fourier Transform
The Cooley-Tukey FFT splits a signal into even and odd halves recursively, T(n) = 2T(n/2) + O(n) = O(n log n). That speed-up over the O(n^2) direct method is what makes audio processing, NumPy's fft and modern signal processing practical.
Regex catastrophic backtracking
Backtracking regex engines try alternatives recursively, so a pattern like (a+)+$ can create an exponential recursion tree on a non-matching input. A regex with catastrophic backtracking caused Cloudflare's global outage in July 2019 by pinning CPUs at 100 percent.
Database external sorting
When an ORDER BY does not fit in memory, PostgreSQL sorts runs and merges them, the same O(n log n) divide and merge structure, which is why its EXPLAIN output reports an external merge sort on disk.
In a project
A pricing service computes the best bundle discount for a cart by recursively trying to include or exclude each item. It is fast in tests with 8 items, but checkout times out for corporate carts with 40 items.
- Draw the recursion tree: two branches per item and depth n, so 2^n calls. 2^8 = 256, but 2^40 is about 1.1 trillion.
- Notice that the result depends only on (item index, remaining budget), so many branches repeat the same subproblem.
- Memoize on that state, reducing the work to O(n x budget levels), or switch to a bottom-up DP.
- Add a load test with a 60-item cart and alert on p99 latency so exponential behaviour cannot come back unnoticed.
Impact: Checkout for large carts drops from timing out to a few milliseconds, and the team has a written complexity analysis showing why, instead of guessing at caching layers.
Trade-offs
Use it when
- You need the complexity of any recursive function: draw the tree first
- The recurrence fits aT(n/b) + O(n^d): apply the master theorem
- Explaining why memoization or a different split will help
Avoid it when
- Applying the master theorem to subtract-style recurrences like T(n - 1) + T(n - 2); it does not fit, use the tree
- Quoting average-case complexity (quicksort O(n log n)) when the interviewer asks about the worst case (O(n^2))
- Ignoring hidden costs like list slicing, which adds O(n) per call
Cost: Time = sum of work over all nodes. Space = maximum depth x frame size + any extra structures. Common results: binary search O(log n), merge sort O(n log n), naive Fibonacci O(2^n) as an upper bound (more precisely about 1.618^n), permutations O(n x n!).
Common mistakes
- Saying space equals the number of calls; it equals the maximum depth, because finished frames are freed.
- Forgetting the work inside each call, such as slicing a list (O(n)) or concatenating strings.
- Calling naive Fibonacci O(n^2) or O(n) instead of exponential.
- Using the master theorem on recurrences that do not divide the input by a constant.
- Ignoring that the worst-case depth of quicksort is O(n), not O(log n).
Interview questions
Quick revision
- Time = sum of work over all nodes of the recursion tree.
- Space = depth of the tree, not its size.
- b branches on n - 1: about b^n calls.
- 2T(n/2) + O(n) = O(n log n); T(n/2) + O(1) = O(log n).
- Master theorem: compare d with log_b(a).
- Naive fib: exponential time, O(n) space.
- Permutations O(n x n!), subsets O(n x 2^n).
Check yourself
1. What is T(n) = 2T(n/2) + O(1)?
2. What is the extra space used by naive recursive fib(n)?
3. How many calls does naive fib(4) make in total, counting fib(4) itself?
4. By the master theorem, what is T(n) = 8T(n/2) + O(n^2)?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.