Recursion Tree Analysis

[!NOTE] The Master Theorem is great, but it has limits. It can’t handle cases like T(n) = T(n/3) + T(2n/3) + n (uneven splits). For these, we need to draw the Recursion Tree.

1. The Method

The goal is to visualize the recursive calls as a tree and sum the work done at each level.

  1. Draw the Tree: Start with the root problem size n. Break it down into children based on the recurrence.
  2. Calculate Work per Node: Determine the non-recursive work done at each node (e.g., n, n<sup>2</sup>, 1).
  3. Sum Work per Level: Add up the work for all nodes at the same depth.
  4. Sum All Levels: Sum the work across all levels (often a Geometric Series).

2. Interactive Tree Builder

Visualize how work propagates through the recursion tree. Let’s analyze T(n) = 2T(n/2) + n (Merge Sort).

Recursion Tree Builder

3. Example Analysis: T(n) = 2T(n/2) + n<sup>2</sup>

Let’s apply the method step-by-step.

  1. Level 0 (Root):
    • Cost: n<sup>2</sup>
    • Nodes: 1
  2. Level 1:
    • Nodes: 2 subproblems of size n/2.
    • Cost per node: (n/2)<sup>2</sup> = n<sup>2</sup> / 4.
    • Total Level Cost: 2 * (n<sup>2</sup> / 4) = n<sup>2</sup> / 2.
  3. Level 2:
    • Nodes: 4 subproblems of size n/4.
    • Cost per node: (n/4)<sup>2</sup> = n<sup>2</sup> / 16.
    • Total Level Cost: 4 * (n<sup>2</sup> / 16) = n<sup>2</sup> / 4.

The Pattern

The series is: n<sup>2</sup> + n<sup>2</sup>/2 + n<sup>2</sup>/4 + ... This is a Geometric Series with ratio r = 1/2.

Since r < 1, the sum is dominated by the first term (the root).

Sum = n2 (1 + 1/2 + 1/4 + ...) = n2 × 2 = O(n2)

This matches Master Theorem Case 3 (Root Heavy).

4. Uneven Splits

What about T(n) = T(n/3) + T(2n/3) + n?

  • The tree is lopsided. The right branch (2n/3) is “heavier” and goes deeper.
  • Shortest Path (Left): Depth log<sub>3</sub> n
  • Longest Path (Right): Depth log_(3/2) n
  • Cost per Level: n (at the top). At the next level: (n/3) + (2n/3) = n.
  • The cost is n for every level until the shortest branch hits a leaf.
  • Total Complexity: O(n log n).

[!TIP] Even with uneven splits, if the sum of fractions (1/3 + 2/3) equals 1, the work per level is constant O(n), leading to O(n log n).

5. Deep Dive Strategy Lab: Recursion Tree Analysis

Intuition Through Analogy

Think of this chapter like trying all lock combinations safely. The goal is not to memorize a fixed trick, but to repeatedly answer:

  1. What is the bottleneck?
  2. Which constraint dominates (time, memory, latency, correctness)?
  3. Which representation makes the bottleneck easier to eliminate?