Recursion Tree Method: Visualizing Recurrence Relations

When analyzing recursive algorithms, you often encounter recurrence relations like T(n) = 2T(n/2) + n. While the Master Theorem provides a quick solution, it doesn't always apply, and it doesn't give you intuition. The recursion tree method fills that gap: it lets you visualize the recursion as a tree, compute the work done at each level, and sum across levels to find the total time complexity. This method is especially useful for recurrences where the Master Theorem fails, such as when the work function is not polynomial or when the recursion is unbalanced. In this tutorial, you'll learn how to draw recursion trees, compute level costs, and derive closed-form solutions. We'll cover common patterns like balanced trees (merge sort), unbalanced trees (quick sort worst-case), and recurrences with fractional divisions. By the end, you'll be able to solve recurrences confidently and understand the performance of recursive algorithms at a glance.

What is a Recursion Tree?

A recursion tree is a visual representation of the recursive calls made by an algorithm. Each node represents a subproblem, and its children represent the recursive calls it makes. The root node corresponds to the original problem of size n. The tree expands until it reaches base cases (size 1 or constant). The total time complexity is the sum of the costs of all nodes. For a recurrence T(n) = aT(n/b) + f(n), the tree has branching factor a, and each child reduces the problem size by a factor of b. The cost at each node is f(n) for the root, f(n/b) for its children, and so on. By summing the costs level by level, we can derive a closed-form expression for T(n).

# Example: Recursion tree for merge sort recurrence T(n) = 2T(n/2) + n
# We'll simulate the tree for n=8
def merge_sort_cost(n):
    if n <= 1:
        return 0
    # cost of dividing and merging: n
    return n + merge_sort_cost(n//2) + merge_sort_cost(n//2)

print(merge_sort_cost(8))  # Output: 24 (which is 8*log2(8) = 8*3 = 24)

Building a Recursion Tree Step by Step

Let's build a recursion tree for T(n) = 2T(n/2) + n. Start with the root node representing T(n) with cost n. Then, draw two children representing T(n/2) each with cost n/2. Continue until you reach base cases (size 1). The tree has log2(n) levels (0 to log2(n)). At level i, there are 2^i nodes, each with cost n/2^i. The total cost at level i is 2^i (n/2^i) = n. Since there are log2(n)+1 levels, total cost = n (log2(n)+1) = O(n log n). This matches the known complexity of merge sort.

# Visualizing the recursion tree for T(n) = 2T(n/2) + n
import math

def tree_level_costs(n):
    levels = int(math.log2(n)) + 1
    costs = []
    for i in range(levels):
        nodes = 2**i
        cost_per_node = n / (2**i)
        total_level_cost = nodes * cost_per_node
        costs.append(total_level_cost)
    return costs

print(tree_level_costs(8))  # [8.0, 8.0, 8.0, 8.0]

Solving Unbalanced Recurrences: T(n) = T(n-1) + n

Not all recurrences are balanced. Consider T(n) = T(n-1) + n, which arises in algorithms like selection sort. The recursion tree is a chain: root cost n, child cost n-1, then n-2, ..., down to 1. There are n levels, and the total cost is the sum of 1 to n = n(n+1)/2 = O(n^2). This is a linear tree, not a branching tree. The recursion tree method still works: draw a single child at each node, sum the costs. For T(n) = T(n-1) + f(n), the total cost is sum_{k=1}^n f(k).

# Recursion tree for T(n) = T(n-1) + n
def total_cost(n):
    if n == 0:
        return 0
    return n + total_cost(n-1)

print(total_cost(5))  # 5+4+3+2+1 = 15

Handling Non-Constant Work per Level: T(n) = 2T(n/2) + n log n

Sometimes the work per node is not a simple polynomial. For example, T(n) = 2T(n/2) + n log n. The recursion tree has log n levels. At level i, there are 2^i nodes, each with cost (n/2^i) log(n/2^i). The total cost at level i is 2^i (n/2^i) log(n/2^i) = n log(n/2^i). Summing over i from 0 to log n, we get n sum_{i=0}^{log n} log(n/2^i) = n sum_{k=0}^{log n} log(2^k) (by letting k = log n - i) = n sum_{k=0}^{log n} k = n (log n)(log n + 1)/2 = O(n log^2 n). This is a case where the Master Theorem does not apply directly (since f(n) is not polynomial), but the recursion tree gives the answer.

# Simulating T(n) = 2T(n/2) + n log n (base 2)
import math
def cost_nlogn(n):
    if n <= 1:
        return 0
    return n * math.log2(n) + cost_nlogn(n//2) + cost_nlogn(n//2)

print(cost_nlogn(8))  # 8*3 + 2*(4*2) + 4*(2*1) + 8*(1*0) = 24 + 16 + 8 + 0 = 48

Recursion Tree for Fractional Divisions: T(n) = T(n/3) + T(2n/3) + n

Some recurrences have uneven splits, like T(n) = T(n/3) + T(2n/3) + n, which appears in quick select or median-of-medians. The recursion tree is not perfectly balanced. The longest path from root to leaf is when we always take the 2n/3 branch, giving height log_{3/2}(n). The shortest path is log_3(n). The work per level is still n (since at each level, the sum of subproblem sizes is n). However, the number of levels is not uniform across all branches. To find an upper bound, we consider the longest path: total cost <= n * (log_{3/2}(n) + 1) = O(n log n). This is a common technique: use the longest path to bound the total work.

# Simulating T(n) = T(n/3) + T(2n/3) + n (approximate)
import math
def cost_fractional(n):
    if n <= 1:
        return 0
    return n + cost_fractional(n//3) + cost_fractional(2*n//3)

print(cost_fractional(9))  # Example: 9 + (3+6) + ...

Common Mistakes and How to Avoid Them

1. Forgetting base case costs: Always include the cost of base cases (usually O(1)). In the tree, leaves have constant cost. If the number of leaves is significant, their total cost may dominate. For T(n) = 2T(n/2) + n, leaves are at level log n, with 2^{log n} = n leaves, each O(1), total O(n). This is already accounted for in the level sum. 2. Incorrect level count: For T(n) = aT(n/b), the tree height is log_b(n). If b is not an integer, use floor/ceil carefully. 3. Assuming uniform level costs: Not all recurrences have constant level costs. Always compute the cost per node and multiply by number of nodes. 4. Ignoring the work at the root: The root cost is f(n), which is often the dominant term. 5. Using Master Theorem when it doesn't apply: The recursion tree is a safer bet.

# Example: Forgetting base case cost leads to wrong sum
# Correct: T(n) = 2T(n/2) + n, with T(1)=1
# Wrong: ignoring T(1) cost
def wrong_cost(n):
    if n <= 1:
        return 0  # should be 1
    return n + wrong_cost(n//2) + wrong_cost(n//2)

print(wrong_cost(8))  # 24, but correct is 24 + 8*1 = 32? Actually base cost is 1 per leaf, 8 leaves -> 8, total 32? Wait, merge sort base case is O(1) but often ignored. In recurrence, T(1)=c, constant. So total = n log n + c*n. For n=8, 8*3 + 8 = 32. But our function gave 24 because we returned 0. So we missed 8.