Introduction
A recurrence relation expresses the running time of a recursive algorithm in terms of the running time of its smaller subproblems, plus the extra work done to combine them. For example, merge sort splits an array of size n into two halves, recursively sorts each half, and merges them in linear time, giving the recurrence T(n) = 2T(n/2) + n. A recursion tree is a visual tool that expands this recurrence level by level, letting us sum up the total work across all levels to find a closed-form running time.
Cricket analogy: Splitting a full scorecard analysis into the first-innings half and second-innings half, each analyzed recursively and then merged in one linear pass, is exactly T(n) = 2T(n/2) + n, and a recursion tree visualizes the total work level by level, over by over, to find the closed-form running time.
Explanation
To build a recursion tree for T(n) = 2T(n/2) + n, the root represents a problem of size n doing n units of non-recursive work, with two children each representing a subproblem of size n/2. Each of those nodes again does non-recursive work proportional to its size and spawns two children of size n/4, and so on. The tree has log2(n) + 1 levels (since the size halves each level, reaching 1 after log2(n) halvings). At level i, there are 2^i nodes, each of size n/2^i, and each doing n/2^i units of work, so the total work at level i is 2^i * (n/2^i) = n — every level contributes exactly n work. Summing n over log2(n)+1 levels gives total work of n*(log2(n)+1) = O(n log n).
Cricket analogy: The root represents the whole season's scorecard doing n units of work, splitting into two half-season nodes, each again splitting into quarter-season nodes, until the tree has log2(n)+1 levels, and at every level the total work sums to n, giving n*(log2(n)+1) total analysis effort.
Example
def merge_sort(arr):
# Base case: a list of 0 or 1 elements is already sorted
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # T(n/2)
right = merge_sort(arr[mid:]) # T(n/2)
return merge(left, right) # O(n) combine step
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge_sort([5, 2, 4, 1, 3, 6])) # [1, 2, 3, 4, 5, 6]Analysis
Recursion tree derivation for T(n) = 2T(n/2) + n: Level 0 (root): 1 node of size n, work = n. Level 1: 2 nodes of size n/2 each, work = 2 * (n/2) = n. Level 2: 4 nodes of size n/4 each, work = 4 * (n/4) = n. Level i (general): 2^i nodes of size n/2^i each, work = 2^i * (n/2^i) = n. The recursion bottoms out when n/2^i = 1, i.e. i = log2(n), giving log2(n) + 1 levels total. Total work = sum over i=0 to log2(n) of n = n * (log2(n) + 1) = O(n log n). This level-by-level accounting is exactly what the recursion tree method formalizes, and it matches the result the Master Theorem gives for this recurrence (case 2, since f(n) = n equals n^(log_b a) = n^1).
Cricket analogy: Level 0 is the full-season review (n work), level 1 splits into two half-season reviews (2*(n/2)=n work), level 2 into four quarter-season reviews (4*(n/4)=n work), continuing until size hits 1 at level log2(n), so total work across log2(n)+1 levels is n*(log2(n)+1) = O(n log n), matching the Master Theorem's case 2.
Key Takeaways
- A recurrence relation like T(n) = aT(n/b) + f(n) captures subproblem count (a), subproblem size (n/b), and combine cost (f(n)).
- A recursion tree expands the recurrence level by level so you can sum the work done at each level.
- For T(n) = 2T(n/2) + n, every level does exactly n total work across log2(n)+1 levels, giving O(n log n).
- Recursion trees are especially useful when the Master Theorem does not directly apply, e.g. non-polynomial f(n) or unequal subproblem sizes.
Practice what you learned
1. In the recurrence T(n) = 2T(n/2) + n, what does the '+n' term represent?
2. How many levels does the recursion tree for T(n) = 2T(n/2) + n have?
3. How much total work is done at level i of the recursion tree for T(n) = 2T(n/2) + n?
4. What is the closed-form solution to T(n) = 2T(n/2) + n derived from the recursion tree?
Was this page helpful?
You May Also Like
The Master Theorem
Apply the Master Theorem's three cases to quickly solve divide-and-conquer recurrences of the form T(n) = aT(n/b) + f(n).
Recursion Basics
Learn how functions that call themselves can solve problems by breaking them into smaller subproblems.
Merge Sort as Divide and Conquer
See how merge sort applies divide, conquer, and combine to achieve guaranteed O(n log n) sorting.