The Recursion-Tree Method

A recurrence relation for an algorithm's running time expresses $T(n)$, the cost on an input of size $n$, in terms of $T$ evaluated at smaller sizes plus some extra work. A typical divide-and-conquer recurrence has the shape

meaning: split the problem of size $n$ into $a$ subproblems each of size $n/b$, solve each recursively, and spend $f(n)$ additional time to divide the input and combine the sub-results. The recursion tree is the literal unrolling of this recurrence into a tree: the root represents the call $T(n)$, labeled with $f(n)$ (the work done at that call, not counting its children); its $a$ children represent the $a$ recursive calls $T(n/b)$, each labeled with $f(n/b)$; and so on, until the subproblem size shrinks to the base case, at which point that branch terminates in a leaf. The key quantity at every level $i$ (root is level $0$) is the per-level cost: the sum of the labels of all nodes at that depth. Because the tree is usually regular near the root (every node at level $i$ has the same subproblem size $n/b^i$, assuming a single split ratio $b$), the per-level cost is often

Summing this expression over all levels $i = 0, 1, \dots, \log_b n$ — the tree's depth, since that is where $n/b^i$ reaches the base-case size — gives the total work, up to the cost paid at the leaves themselves (the base-case cost times the number of leaves, $a^{\log_b n}$). The word "guess" matters: this sum is exact for the idealized recurrence with $n$ a power of $b$ and integer sizes throughout, and it is a strong heuristic even when those assumptions are informally violated, but the resulting closed form must still be verified rigorously — typically by the substitution method (assume the bound, plug it back into the recurrence, check the algebra closes with the right constants) — before it counts as a proof. This connects the recursion tree directly to the Substitution Method as its natural verification partner, and it is the intuitive engine behind the three cases of the Master Theorem, which is really a theorem about which level of the tree dominates the sum.

Building and evaluating a recursion tree is a mechanical five-step process. The steps are the same whether the tree turns out to be balanced (Master-Theorem territory) or unbalanced (where the tree method is indispensable).

Step 1 — Draw the root. Label it with $f(n)$, the non-recursive work at the top-level call.

Step 2 — Expand one level. Replace the root's recursive part $a\,T(n/b)$ with $a$ children, each labeled $f(n/b)$, representing the non-recursive work of each of those $a$ subcalls.

Step 3 — Recurse the expansion. Keep expanding every non-leaf node the same way. At depth $i$, there are $a^i$ nodes, each of a subproblem of size $n/b^i$ and each labeled $f(n/b^i)$ — provided the split is uniform (single $a$ and $b$ throughout). If different children shrink by different factors, track each branch's size separately; the tree becomes irregular and levels must be summed less mechanically (this is precisely the "unbalanced" case treated in the worked example below).

Step 4 — Find the depth and the leaves. The recursion bottoms out when the subproblem size hits the base case, i.e. when $n/b^i = \Theta(1)$, giving depth $i^* = \log_b n$. The number of leaves is $a^{i^*} = a^{\log_b n} = n^{\log_b a}$ (a rewriting identity worth memorizing, since it is exactly the exponent that appears in the Master Theorem). Each leaf costs $\Theta(1)$ for its base case.

Step 5 — Sum every level, then sum the levels. Compute

the first term collecting all the internal (non-leaf) work level by level, the second collecting the total leaf cost. Then examine the resulting series: does it grow, shrink, or stay flat as $i$ increases? That determines whether the root, the leaves, or every level "equally" governs the asymptotics. ``` RECURSION-TREE-ESTIMATE(a, b, f, n): // Conceptually builds and sums the recursion tree for // T(n) = a T(n/b) + f(n), base case T(1) = Θ(1). depth ← ceil(log_b(n)) // number of internal levels total ← 0 for i ← 0 to depth - 1: nodes_at_level_i ← a^i size_at_level_i ← n / b^i cost_per_node ← f(size_at_level_i) level_cost ← nodes_at_level_i cost_per_node total ← total + level_cost // record level_cost[i] for inspection — this is // the sequence whose growth pattern reveals the answer leaves ← a^depth // = n^(log_b a) total ← total + leaves Θ(1) // base-case cost per leaf return total // typically expressed in closed form after // recognizing the series (geometric, arithmetic, // or harmonic) that level_cost[i] forms ``` The pseudocode is deliberately explicit about recording* `level_cost[i]` as a sequence, because that sequence is exactly what you inspect by eye to classify the recurrence: is it increasing geometrically with $i$ (root-heavy — total is $\Theta(f(n))$, dominated by the top), decreasing geometrically (leaf-heavy — total is $\Theta(n^{\log_b a})$, dominated by the bottom), or constant across levels (balanced — total is $\Theta(f(n)\log n)$, since there are $\Theta(\log n)$ equal-cost levels)? These three outcomes are exactly the three cases of the Master Theorem, though the tree method applies even when $f(n)$ is not a clean polynomial, or when the split is not uniform.

Deriving the closed form. For $T(n) = a T(n/b) + f(n)$, the recursion tree gives

where the second term is the total leaf cost (there are $n^{\log_b a}$ leaves, each $\Theta(1)$). The sum is a series in $i$; its behavior falls into three regimes, matching the Master Theorem's three cases:

• Leaves dominate. If $a^i f(n/b^i)$ decreases geometrically as $i$ grows (each level contributes strictly less than a constant fraction of the level above), the sum is dominated by its last term and $T(n) = \Theta(n^{\log_b a})$. This happens when $f(n) = O(n^{\log_b a - \epsilon})$ for some $\epsilon > 0$.
• All levels contribute equally. If $a^i f(n/b^i)$ stays the same order of magnitude at every level, there are $\Theta(\log n)$ levels each contributing $\Theta(f(n))$, giving $T(n) = \Theta(f(n) \log n)$. This happens when $f(n) = \Theta(n^{\log_b a})$.
• The root dominates. If $a^i f(n/b^i)$ increases geometrically as $i$ grows, the sum is dominated by its first term ($i=0$), giving $T(n) = \Theta(f(n))$. This happens when $f(n) = \Omega(n^{\log_b a + \epsilon})$, subject to a regularity condition on $f$.

This is exactly the trichotomy formalized by the Master Theorem — the recursion tree is the reasoning that makes that theorem believable rather than an arbitrary rule to memorize.

Why the tree method is only a guess-generator, not a proof by itself. The per-level sum above assumes an idealized regular tree: $n$ a power of $b$, every subproblem exactly $n/b^i$, and the sum over $i$ evaluated as an infinite or exact geometric series with clean closed forms. Real recurrences involve floors and ceilings ($T(\lceil n/2 \rceil)$), possibly non-uniform splits, and lower-order terms that the loose tree-level arithmetic can obscure. The standard remedy is: use the tree to conjecture a bound $T(n) = O(g(n))$ (or $\Theta$, or $\Omega$), then verify it by the substitution method — assume $T(k) \le c\, g(k)$ for all $k < n$, substitute into the recurrence, and check that the algebra produces $T(n) \le c\, g(n)$ for a suitable constant $c$ and all $n$ beyond some threshold $n_0$. This two-step discipline (tree for intuition, substitution for rigor) is standard practice, because the tree's informal handling of floors/ceilings and boundary terms can, in principle, hide an extra logarithmic factor or an incorrect constant.

Complexity of using the method itself. Constructing the recursion tree conceptually and summing $\Theta(\log_b n)$ levels, each requiring a constant amount of series-recognition work, takes $O(\log n)$ "reasoning steps" — this is a pen-and-paper analysis technique, not an algorithm that runs on the target machine, so its own "cost" is about proof effort, not runtime. The value of the method is that it turns an open-ended guess into a structured, level-by-level bookkeeping exercise that rarely misses a term.

Honesty about tradeoffs. The recursion tree is superb for building intuition and for handling recurrences the Master Theorem cannot (unbalanced splits, recurrences with $f(n)$ containing logs, recurrences like $T(n) = T(n/3) + T(2n/3) + n$). It is comparatively weak at producing tight, constant-exact bounds without a follow-up substitution proof, and for deeply irregular trees the level sums themselves can become intricate enough that a direct inductive guess-and-check (skipping the tree) is faster in practice. The tree method's real strength is diagnostic: it tells you which closed form to attempt, even when it cannot, by itself, certify that form.

Consider the unbalanced recurrence

which arises, for instance, from a partitioning-based algorithm with a 1:2 split (a lopsided variant of the recurrence for Quicksort-style divide-and-conquer, or from certain selection algorithms). This recurrence has two different branch sizes, so it does not fit the single-ratio $a\,T(n/b)+f(n)$ template the Master Theorem requires — this is exactly where the recursion tree earns its keep, because the tree still makes sense even though the levels are no longer perfectly regular.

Building the tree. The root has cost $n$ and two children: one subproblem of size $n/3$, one of size $2n/3$. Each of those has cost equal to its own size (since $f(n) = n$ is linear, the cost at a node of size $m$ is $m$), and each spawns two further children in the same $1{:}2$ ratio.

Observation 1 — every level sums to (at most) $n$. At the root: cost $n$. At depth 1: costs $n/3$ and $2n/3$, summing to exactly $n$. At depth 2, the four nodes have sizes $n/9,\ 2n/9,\ 2n/9,\ 4n/9$ — again summing to exactly $n$. In general, since each node's cost equals its size, and each node's two children's sizes sum to exactly the parent's size (because $1/3 + 2/3 = 1$), every level's total cost is exactly $n$, regardless of how unevenly that $n$ is distributed among the nodes at that level.

Observation 2 — the tree's depth is between $\log_3 n$ and $\log_{3/2} n$. The shortest root-to-leaf path always takes the $n/3$ branch, shrinking fastest, reaching the base case after $\log_3 n$ steps. The longest path always takes the $2n/3$ branch, shrinking slowest, reaching the base case after $\log_{3/2} n$ steps. Both quantities are $\Theta(\log n)$ (only the constant inside differs), so the tree has $\Theta(\log n)$ levels overall — it is not perfectly regular, but it is depth-bounded on both sides by a constant multiple of $\log n$.

Summing. Since each of the $\Theta(\log n)$ levels contributes $\Theta(n)$ (at most exactly $n$, and — checking the shortest branch doesn't terminate too early to make levels contribute less — at least $\Omega(n)$ for all levels down to depth $\log_3 n$), the total is

The table below traces the level-by-level costs numerically for $n = 720$ (chosen for divisibility), rounding node sizes to nearest integer for illustration:

With $n = 720$ and roughly $11$ "full" levels before the tree finishes tapering off into a mix of leaves and internal nodes, the total is on the order of $n \times \Theta(\log n) \approx 720 \times 9.5 \approx 6800$–$8000$, consistent with $\Theta(n \log n)$. (The exact constant depends on rounding and the base case, which the tree method does not need to pin down — only the growth rate $\Theta(n\log n)$ is claimed here.)

Verifying by substitution. Guess $T(n) \le c\, n \log n$ for constants $c>0$, $n_0$, all $n \ge n_0$. Assume it holds for all inputs smaller than $n$:

Expanding $\log(n/3) = \log n - \log 3$ and $\log(2n/3) = \log n - \log(3/2)$, and collecting terms, gives

The bracketed constant $\tfrac13\log 3 + \tfrac23 \log \tfrac32$ is strictly positive (numerically $\approx 0.918$ in base-2 logs), so for $c$ large enough that $c \cdot 0.918 \ge 1$, the extra $+n$ is absorbed and $T(n) \le c\,n\log n$ follows — confirming the tree-derived guess $\Theta(n\log n)$ rigorously.

The recursion tree is less the invention of one individual and more a standard visualization that crystallized as divide-and-conquer algorithm analysis matured through the 1960s–1980s, alongside the formal statement of the Master Theorem. Its logical ancestor is the general study of recurrence relations in combinatorics and numerical analysis, but its specific role as a pedagogical device for algorithm complexity — draw the tree, sum the levels, guess the closed form — was popularized through algorithms textbooks and courses that needed an intuitive bridge between recursive pseudocode and asymptotic notation.

Recursion-tree reasoning underlies the complexity analysis of virtually every divide-and-conquer algorithm taught and deployed in practice: Merge Sort ($T(n)=2T(n/2)+n$, tree gives $\Theta(n\log n)$), Quicksort's average-case and worst-case recurrences, Binary Search's degenerate single-branch tree, Strassen's matrix multiplication ($T(n) = 7T(n/2) + \Theta(n^2)$, revealing the sub-cubic $\Theta(n^{\log_2 7})$ bound), and the Fast Fourier Transform's $T(n) = 2T(n/2) + \Theta(n)$ recurrence that gives the $\Theta(n\log n)$ bound underlying signal processing, audio/video codecs, and large-scale numerical libraries. Compiler writers and systems engineers reason about recursive algorithms' cache behavior and parallel span using the same level-by-level decomposition, since a recursion tree's depth also bounds the span (critical path length) of a parallel divide-and-conquer computation, directly informing scheduling and load-balancing decisions in parallel runtime systems. Database query planners and computational geometry libraries (closest-pair, convex hull) rely on the same style of recurrence to certify $\Theta(n\log n)$ performance guarantees before code ever ships, and interview-style algorithm assessments at technology companies routinely test exactly this skill — sketch the tree, sum the levels, name the bound — as a proxy for a candidate's ability to reason about scalability without running benchmarks.

Ask the tutor: Can you show how the recursion tree handles a recurrence with a logarithmic driving function, like $T(n) = 2T(n/2) + n\log n$?