7.3 Divide-and-Conquer Recurrences and Recursion Trees

Section 7.2 related one sequence term to earlier terms. We now return to the algorithmic cost functions from Chapter 5.

A recursive algorithm solves a problem by calling itself on smaller inputs. If its input size is $n$, its operation count is not obtained from one loop alone: it includes the work done by every recursive call.

A recurrence lets us record that entire dependency structure.

From an algorithm to a cost recurrence

A divide-and-conquer algorithm has three conceptual stages:

1. divide the input into smaller subproblems; 2. conquer the subproblems recursively; 3. combine their answers.

Let $T(n)$ denote the cost of solving an input of size $n$. A common recurrence is

Every symbol has a specific meaning:

• $a$ is the number of recursive subproblems created by one non-base call;
• $b$ is the factor by which each subproblem's size shrinks;
• $n/b$ is therefore the size of each subproblem;
• $f(n)$ is the nonrecursive divide-and-combine work performed by the current call.

We assume $a\ge1$ and $b>1$. To keep the first calculations exact, we often take $n$ to be a power of $b$. Floors and ceilings change endpoint details but usually not the asymptotic class.

A recurrence also needs a base cost. We will use

where $d>0$ is a constant.

Example: binary search makes one smaller call

Binary search compares a target with the middle array element and continues in only one half. If the comparison and index updates cost a constant $c$, then

Unfold once:

After $i$ unfoldings,

The base case is reached when

Therefore $2^i=n$ and

Substitution gives

This is the halving-loop behavior from Chapter 5 expressed recursively.

A recursion tree displays every call

Repeated algebra can hide where work occurs. A recursion tree represents:

• one recursive call as one node;
• its recursive subcalls as children;
• the node's nonrecursive work as a cost label.

For

level $0$ contains the original call. Level $1$ contains its children, and so on.

At level $i$:

• the number of nodes is $a^i$;
• each node handles size $n/b^i$;
• each node contributes $f(n/b^i)$ nonrecursive work;
• the total nonrecursive cost of the level is

The leaves occur when $n/b^h=1$. Solving gives the tree height

The number of leaves is

The identity $a^{\log_b n}=n^{\log_b a}$ converts the leaf count into a power of $n$. The exponent $\log_b a$ measures how quickly recursive demand grows while input size shrinks.

Example: merge sort has equal work per internal level

Merge sort creates two subproblems of size $n/2$ and merges their sorted results in linear time. Its recurrence is

At level $i$:

• there are $2^i$ calls;
• each call handles $n/2^i$ items;
• each call performs $c(n/2^i)$ merge work.

Thus the level cost is

The number of internal levels is $\log_2 n$. Summing their equal costs gives

There are $2^{\log_2 n}=n$ leaves, each costing $d$, so leaf cost is $dn$. Therefore

The factor $n$ comes from the work across one level; the factor $\log n$ comes from the number of levels.

Direct an animated recursion-tree performance. Expand exactly one level at a time, inspect every call's input and local cost, and watch nodes combine into a level-cost strip. Presets for binary search, merge sort, and four-way recursion make one path, balanced levels, and leaf explosions visibly different.

Three ways recursion-tree cost can be distributed

The total cost is the sum of all level costs plus the leaf costs. Depending on the recurrence, most work may lie near the root, be balanced across levels, or accumulate near the leaves.

Suppose the nonrecursive work is a power

where $c>0$ and $d\ge0$. At level $i$,

The ratio

tells how the cost changes from one level to the next.

Root-heavy: $\rho<1$

If $a<b^d$, level costs shrink geometrically. The top levels dominate, and

Example:

Here $a=2$, $b=2$, and $d=2$, so $\rho=2/4=1/2$.

Balanced: $\rho=1$

If $a=b^d$, every internal level has the same asymptotic cost. Multiplying by the number of levels gives

Merge sort is the example $a=2$, $b=2$, $d=1$, so $\rho=1$.

Leaf-heavy: $\rho>1$

If $a>b^d$, level costs grow geometrically. The bottom of the tree dominates, and the leaf count determines the order:

For

we have $\rho=4/2=2$. The number of leaves is

so $T(n)\in\Theta(n^2)$.

The simplified Master Theorem

The three comparisons above form a useful version of the Master Theorem. For

with $a\ge1$, $b>1$, $d\ge0$, and the usual regularity assumptions, compare $d$ with $\log_b a$:

This version covers polynomial combine costs. More general forms of the theorem handle logarithmic factors and require more precise conditions; we do not need those extensions here.

A disciplined use procedure

For a new recurrence:

1. identify $a$, $b$, and $f(n)$ from the algorithm; 2. state the base case; 3. if $f(n)=\Theta(n^d)$, compute $d$ and $\log_b a$; 4. select the matching case; 5. check the conclusion against a recursion-tree level cost.

The last check matters. A memorized case number is fragile; the tree explains why the answer has that growth rate.

When the Master Theorem does not apply directly

The displayed form does not directly handle every recurrence. Examples include:

because the subproblem is $n-1$, not $n/b$, and

because the subproblems have unequal sizes.

Such recurrences may still be analyzed by unfolding, substitution, or a more general recursion-tree argument. A theorem is a tool with hypotheses, not a formula to apply by appearance alone.

Tune branching $a$, shrink factor $b$, and combine exponent $d$ in a workload arena. Recursive demand and local work race down synchronized levels; before revealing the result, place your prediction on root-heavy, balanced, or leaf-heavy. The arena then exposes the ratio $a/b^d$ and the matching asymptotic certificate.

Chapter bridge

Chapter 7 connected construction, counting, proof, and algorithms. Recursive definitions generated legal objects; structural induction followed their constructors; recurrence relations counted smaller cases; and recursion trees summed the work of recursive algorithms.

Chapter 8 turns to integers. Divisibility and prime factorization will provide the structure needed for modular arithmetic and cryptography, while recursive reasoning will reappear in Euclid's algorithm.