Example Problems - Recursion Tree Method

 

Problem-1

Irregular Example Using the Recursion Tree Method

Solve the recurrence

$$\boxed{T(n)=T(n/3)+T(2n/3)+\Theta(n)}$$

using the Recursion Tree Method.

---

Step 1: Understand the Recurrence

The recurrence consists of

• One subproblem of size $\frac n3$
• One subproblem of size $\frac{2n}{3}$
• Linear work outside recursion

Thus,

$$a=2$$

but unlike Merge Sort,

the two recursive calls are not equal.

---

Why is this recurrence irregular?

Compare it with Merge Sort.

Merge Sort

$$T(n)=2T(n/2)+n$$

Every recursive call produces

           n

        /      \

      n/2      n/2

Both branches have the same height.

---

Present Recurrence

$$T(n)=T(n/3)+T(2n/3)+n$$

                n

          /             \

       n/3            2n/3

The left branch shrinks much faster than the right branch.

Hence,

the recursion tree is unbalanced.

This is exactly  an irregular example.

---

Step 2: Draw the First Few Levels

                     n
                  Cost = cn

               /            \

            n/3            2n/3
          Cost            Cost

        /     \          /      \

     n/9   2n/9      2n/9     4n/9

Notice

Left child:

$$\frac13$$

Right child:

$$\frac23$$

Each level continues similarly.

---

Step 3: Cost of Each Level

The root performs

$$cn$$

units of work.

---

Level 1

Nodes

$$\frac n3,\qquad\frac{2n}3$$

Cost

$$c\frac n3 + c\frac{2n}3 = cn$$

---

Level 2

Nodes

$$\frac n9,\quad \frac{2n}9,\quad \frac{2n}9,\quad \frac{4n}9$$

Total cost

$$c \left( \frac19+\frac29+\frac29+\frac49 \right)n = cn$$

Again,

the level cost is

$$cn.$$

---

General Observation

At every level,

the subproblem sizes always add up to

$$n.$$

Therefore,

every level contributes

$$\boxed{cn}$$

---

Step 4: Height of the Tree

Unlike Merge Sort,

there is no single height.

Different branches stop at different times.

---

Leftmost Branch

Each level divides by

$$3.$$

Problem size after

$$i$$

levels

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

Stop when

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

Thus,

$$i=\log_3 n.$$

---

Rightmost Branch

Each level divides only by

$$\frac32$$

because

$$n \rightarrow \frac23n.$$

After

$$i$$

levels,

problem size

$$\left(\frac23\right)^i n.$$

Stop when

$$\left(\frac23\right)^in=1.$$

Taking logarithms,

$$\boxed{ i=\log_{3/2}n }$$

 The rightmost branch determines the maximum height of the recursion tree.

---

Step 5: Total Cost of Internal Nodes

We found

Every level costs

$$cn.$$

Height

$$\Theta(\log n).$$

Therefore,

$$\boxed{ \text{Total Internal Cost} = cn\times\Theta(\log n) = O(n\log n) }$$

---

Step 6: What About the Leaves?

At first glance,

one might think

"The tree is binary. Therefore, the number of leaves must be about $2^h$"

 this reasoning is incorrect.

---

Incorrect Analysis

Height

$$\log_{3/2}n$$

Hence,

complete binary tree

contains

$$2^{\log_{3/2}n} = n^{\log_{3/2}2}$$

Since

$$\log_{3/2}2 \approx1.71,$$

this suggests

$$O(n^{1.71})$$

leaves.

This would imply

$$O(n^{1.71})$$

leaf cost,

which is larger than

$$O(n\log n).$$

But this conclusion is not correct because the recursion tree is not a complete binary tree. Most branches terminate earlier, especially those repeatedly taking the $n\mathrm{/}\mathrm{3\; branch.}$

---

Step 7: Counting Leaves Properly

Instead of guessing,

 a new recurrence is introduced

Let

$$L(n)$$

be the number of leaves.

Then

$$\boxed{ L(n) = L(n/3) + L(2n/3) }$$

with

$$L(n)=1$$

for small $n$.

Notice that this recurrence is the same as the original one but without the $+n$ term.

---

Step 8: Solve the Leaf Recurrence

Assume

$$L(n)\le dn.$$

Substitute

$$\begin{aligned} L(n) &= L(n/3)+L(2n/3)\\ &\le d\frac n3 + d\frac{2n}3\\ &= dn. \end{aligned}$$

Thus,

$$\boxed{ L(n)=O(n) }$$

We can  prove the matching lower bound as an exercise, yielding

$$\boxed{ L(n)=\Theta(n). }$$

---

Step 9: Cost of Leaves

Each leaf contributes

$$\Theta(1).$$

Number of leaves

$$\Theta(n).$$

Therefore,

$$\boxed{ \text{Leaf Cost} = \Theta(n). }$$

---

Step 10: Final Cost

Internal nodes

$$O(n\log n)$$

Leaves

$$\Theta(n)$$

Therefore,

$$T(n) = O(n\log n) + \Theta(n) = O(n\log n).$$

We can  prove the matching lower bound by substitution, giving the tight result

$$\boxed{ T(n)=\Theta(n\log n). }$$

---

Summary

Step	Result
Recurrence	$T(n)=T(n/3)+T(2n/3)+n$
Tree type	Unbalanced (irregular)
Cost per level	$cn$
Maximum height	$\Theta(\log n)$ (specifically, $\log_{3/2}n$)
Total internal-node cost	$O(n\log n)$
Number of leaves	$\Theta(n)$
Total leaf cost	$\Theta(n)$
Overall running time	$\boxed{\Theta(n\log n)}$

Problem-2

Solve

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

using

1. Recursion Tree Method
2. Substitution Method ( verify )

---

Part I: Recursion Tree Method

Step 1: Draw the Recursion Tree

The recurrence is

$$T(n)=T(n/2)+n^3$$

Each recursive call produces one subproblem of size $n/2$.

                    n
                 Cost = cn³
                     |
                     |
                  n/2
            Cost = c(n/2)³
                     |
                     |
                  n/4
            Cost = c(n/4)³
                     |
                     |
                  n/8
            Cost = c(n/8)³
                     |
                    ...

Unlike Merge Sort, this tree has only one node at each level.

---

Step 2: Cost at Each Level

Level 0

$$cn^3$$

---

Level 1

$$c\left(\frac n2\right)^3 = \frac18cn^3$$

---

Level 2

$$c\left(\frac n4\right)^3 = \frac1{64}cn^3$$

---

Level 3

$$c\left(\frac n8\right)^3 = \frac1{512}cn^3$$

---

Pattern

At level $i$,

Problem size

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

Cost

$$\boxed{ c\left(\frac n{2^i}\right)^3 = \frac{cn^3}{8^i} }$$

---

Step 3: Height of the Tree

Recursion stops when

$$\frac n{2^h}=1$$

Therefore,

$$2^h=n$$

Hence,

$$\boxed{ h=\log_2n }$$

---

Step 4: Total Cost

Add all levels.

$$T(n) = cn^3 +\frac18cn^3 +\frac1{64}cn^3 +\cdots$$

This is a geometric series with ratio

$$\frac18.$$

Therefore,

$$T(n) = cn^3 \left( 1+\frac18+\frac1{64}+\cdots \right).$$

Using

$$\sum_{i=0}^{\infty}r^i = \frac1{1-r},$$

where

$$r=\frac18,$$
$$= cn^3 \left( \frac1{1-\frac18} \right) = cn^3 \left( \frac87 \right).$$

Hence,

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

---

Step 5: Guess

From the recursion tree,

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

---

Part II: Verify Using the Substitution Method

Step 1: Guess

Assume

$$\boxed{ T(n)\le cn^3 }$$

for some constant $c>0$

---

Step 2: Induction Hypothesis

Assume

$$T(n/2)\le c\left(\frac n2\right)^3.$$

---

Step 3: Substitute

The recurrence is

$$T(n)=T(n/2)+n^3.$$

Substitute the induction hypothesis.

$$\begin{aligned} T(n) &\le c\left(\frac n2\right)^3+n^3. \end{aligned}$$

---

Step 4: Simplify

$$\left(\frac n2\right)^3 = \frac{n^3}{8}.$$

Hence,

$$\begin{aligned} T(n) &\le \frac c8n^3+n^3\\ &= \left(\frac c8+1\right)n^3. \end{aligned}$$

---

Step 5: Choose the Constant

We want

$$T(n)\le cn^3.$$

Therefore,

$$\frac c8+1 \le c.$$

Solve.

$$\begin{aligned} 1 &\le c-\frac c8\\ &= \frac78c. \end{aligned}$$

Hence,

$$\boxed{ c\ge\frac87. }$$

Choose

$$\boxed{ c=2. }$$

Then

$$T(n)\le2n^3.$$

Thus, the induction step is proved.

---

Step 6: Base Case

Choose $c$ large enough so that

$$T(1)\le c.$$

Hence,

the base case holds.

---

Conclusion

Therefore,

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

---

Showing the Tight Bound

To prove

$$\Theta(n^3),$$

prove the lower bound.

Assume

$$T(n)\ge dn^3.$$

Then

$$\begin{aligned} T(n) &\ge d\left(\frac n2\right)^3+n^3\\ &= \frac d8n^3+n^3\\ &= \left(\frac d8+1\right)n^3. \end{aligned}$$

We require

$$\frac d8+1 \ge d.$$

This gives

$$d\le\frac87.$$

Choose

$$d=1.$$

Hence,

$$T(n)=\Omega(n^3).$$

Therefore,

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