Seeing a recurrence as a tree
When the master theorem does not fit, the recursion tree method gives an intuitive way to solve a recurrence. You expand the recursion into a tree where each node is a subproblem and its children are the smaller calls it spawns.
Building the tree
- The root holds the original problem and the combine work done at the top level.
- Each node branches into its subproblems, and each level represents one depth of recursion.
- The leaves are the base cases where the recursion stops.
Summing the work
To get the total cost, you sum the work across the tree.
- Compute the work done at each level by multiplying the number of nodes at that level by the per node cost.
- Add the level totals from root to leaves.
- Often the per level total forms a pattern, such as staying constant, shrinking geometrically, or growing, which determines whether the root, leaves, or all levels dominate.
Why it builds intuition
The tree exposes exactly where the cost concentrates, which the master theorem only summarizes. It also handles uneven splits that the standard form cannot.
Key idea
The recursion tree method expands a recurrence into a tree of subproblems, sums the work level by level, and reveals whether the root, the leaves, or every level dominates the total cost.