The Recursion Tree Method for Solving Recurrences

Introduction

Many Divide-and-Conquer algorithms produce recurrence relations describing their running time.

For example,

• Merge Sort
• Quick Sort
• Binary Search
• Matrix Multiplication
• Strassen's Algorithm

To determine the running time, we must solve these recurrences.

Several techniques are available:

1. Substitution Method
2. Recursion Tree Method
3. Master Method

The Recursion Tree Method is one of the most intuitive techniques because it represents the recursive calls as a tree.

Recursion tree is often used to generate intuition and make a good guess for the solution, which can later be proved rigorously using the substitution method. If the tree is constructed carefully, it can also serve as a direct proof.

---

What is a Recursion Tree?

A recursion tree is a tree representation of the recursive calls made by an algorithm.

Each node in the tree represents

• one recursive subproblem
• and the work performed at that recursive call.

The total running time is obtained by

1. computing the cost of every level,
2. adding the costs of all levels.

---

3. General Procedure

Suppose the recurrence is

$$T(n)=aT(n/b)+f(n)$$

The recursion tree is constructed as follows.

Step 1

Draw the root node.

The root represents the original problem of size

$$n$$

with cost

$$f(n)$$

---

Step 2

Expand the root.

It generates

$$a$$

children.

Each child has problem size

$$\frac{n}{b}$$

---

Step 3

Continue recursively.

Every child again produces

$$a$$

children.

---

Step 4

Stop when the base case is reached.

---

Step 5

Compute

• cost at each node
• cost at each level
• height of the tree

---

Step 6

Add all level costs.

---

4. Example 

Consider the recurrence

$$\boxed{ T(n)=3T(n/4)+cn^2 }$$

where

$$c>0$$

is a constant.

---

Step 1: Draw the Root

The root corresponds to the original problem.

            n

       Cost = cn²

---

Step 2: Expand the Root

The recurrence contains

$$3T(n/4)$$

Therefore,

• three recursive calls
• each of size

$$n/4$$

                 n
             Cost=cn²

        /        |        \

      n/4      n/4      n/4

---

Each child contributes

$$c\left(\frac n4\right)^2$$

---

Step 3: Expand Again

Each

$$n/4$$

problem again becomes

three problems of size

$$n/16$$

                     n

            /         |         \

        n/4         n/4        n/4

      / | \       / | \      / | \

Now there are

$$3^2=9$$

nodes.

Each has cost

$$c\left(\frac n{16}\right)^2$$

---

5. Cost at Each Level

Level 0

One node.

Cost

$$cn^2$$

---

Level 1

Number of nodes

$$3$$

Cost of each node

$$c\left(\frac n4\right)^2 = \frac{cn^2}{16}$$

Total cost

$$3\times\frac{cn^2}{16} = \frac{3}{16}cn^2$$

---

Level 2

Number of nodes

$$3^2$$

Cost of each

$$c\left(\frac n{16}\right)^2 = \frac{cn^2}{16^2}$$

Total

$$\left(\frac3{16}\right)^2cn^2$$

---

General Level $i$

At depth $i$,

Number of nodes

$$3^i$$

Problem size

$$\frac n{4^i}$$

Cost of each node

$$c\left(\frac n{4^i}\right)^2$$

Total level cost

$$3^i c \left(\frac n{4^i}\right)^2 = \left(\frac3{16}\right)^i cn^2$$

---

6. Height of the Tree

Each level reduces the problem size by

$$4$$

After

$$i$$

levels,

problem size becomes

$$\frac n{4^i}$$

Recursion stops when

$$\frac n{4^i}=1$$

Therefore,

$$4^i=n$$

Taking logarithm,

$$i=\log_4 n$$

Hence,

the tree height is

$$\boxed{\log_4 n}$$

---

7. Cost of the Leaves

Number of leaves

$$3^{\log_4 n}$$

Using the logarithm identity

$$a^{\log_b n} = n^{\log_b a}$$

we obtain

$$3^{\log_4 n} = n^{\log_43}$$

Each leaf costs

$$\Theta(1)$$

Therefore,

Leaf cost

$$\Theta(n^{\log_43})$$

---

8. Total Cost

Now sum all levels.

$$T(n) = cn^2 + \frac3{16}cn^2 + \left(\frac3{16}\right)^2cn^2 +\cdots + \Theta(n^{\log_43})$$

Notice

$$\frac3{16}<1$$

Therefore,

the first terms form a geometric series.

Using the geometric series formula,

$$1+r+r^2+\cdots = \frac1{1-r}$$

we get

$$T(n) = \frac{16}{13}cn^2 + \Theta(n^{\log_43})$$

Since

$$\log_43\approx0.792$$
$$n^{0.792} = O(n^2)$$

Therefore,

$$\boxed{T(n)=O(n^2)}$$

Because the first recursive call already contributes $\Omega(n^2)$, we also have the matching lower bound, giving

$$\boxed{T(n)=\Theta(n^2)}$$

---

Why Does the Root Dominate?

Observe the level costs.

Level	Cost
0	$cn^2$
1	$\frac{3}{16}c{n}^2$
2	$(3/16)^2cn^2$
3	$(3/16)^3cn^2$

Every level becomes

$$\frac3{16}$$

times the previous one.

Hence,

the costs decrease geometrically.

The root contributes the largest cost.

This is why

$$T(n)=\Theta(n^2)$$

---

Verification Using Substitution

Next verifies the guess by induction.

Assume

$$T(n)\le dn^2$$

Substitute into the recurrence:

$$T(n) \le 3d\left(\frac n4\right)^2 + cn^2$$
$$= \frac3{16}dn^2 + cn^2$$

To satisfy

$$T(n)\le dn^2$$

it is sufficient to choose

$$d\ge\frac{16}{13}c$$

Thus,

$$\boxed{T(n)=\Theta(n^2)}$$

The recursion tree provided the correct guess, and substitution proved it.

---

General Guidelines for the Recursion Tree Method

When solving any recurrence:

1. Write the recurrence.
2. Draw the recursion tree.
3. Find the number of nodes at each level.
4. Find the size of each subproblem.
5. Compute the cost of each node.
6. Compute the total cost at each level.
7. Find the height of the tree.
8. Sum all level costs.
9. Simplify the resulting expression.

---

Advantages

• Easy to visualize recursive calls.
• Helps understand Divide-and-Conquer algorithms.
• Gives intuition for the solution.
• Useful for deriving the Master Theorem.

---

Limitations

• Can become cumbersome for complex recurrences.
• Summing level costs may require ingenuity.
• Usually provides an educated guess, which should ideally be verified using the substitution method.
• Less convenient than the Master Theorem when the recurrence fits the Master Theorem directly.

---

Key Observations

• Every node represents one recursive subproblem.
• The cost at a node is the non-recursive work performed at that call.
• The number of nodes increases according to the number of recursive calls.
• The subproblem size decreases according to the recurrence.
• The height depends on how quickly the problem size shrinks.
• The total running time is obtained by adding the costs of all levels.
• The recursion tree method is primarily an intuition-building tool  and often serves as a bridge to the substitution method for a rigorous proof.