**Recursion Tree-**

- Like
**Master’s Theorem**, Recursion Tree is another method for solving the recurrence relations. - A recursion tree is a tree where each node represents the cost of a certain recursive sub-problem.
- We sum up the values in each node to get the cost of the entire algorithm.

**Steps to solve Recurrence relations using Recursion tree method-**

**Step-01:**

Draw a recursion tree based on the given recurrence relation.

**Step-02:**

Determine-

- Cost of each level
- Total number of levels in the recursion tree
- Number of nodes in the last level
- Cost of the last level

**Step-03:**

Add cost of all the levels of the recursion tree and simplify the expression so obtained in terms of asymptotic notation.

Following problems clearly illustrates how to apply these steps.

**PRACTICE PROBLEMS BASED ON RECURSION TREE-**

**Problem-01:**

Solve the following recurrence relation using recursion tree method-

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

**Solution-**

**Step-01:**

Draw a recursion tree based on the given recurrence relation.

The given recurrence relation shows-

- A problem of size n will get divided into 2 sub-problems of size n/2.
- Then, each sub-problem of size n/2 will get divided into 2 sub-problems of size n/4 and so on.
- At the bottom most layer, the size of sub-problems will reduce to 1.

This is illustrated through following recursion tree-

The given recurrence relation shows-

- The cost of dividing a problem of size n into its 2 sub-problems and then combining its solution is n.
- The cost of dividing a problem of size n/2 into its 2 sub-problems and then combining its solution is n/2 and so on.

This is illustrated through following recursion tree where each node represents the cost of the corresponding sub-problem-

**Step-02:**

Determine cost of each level-

- Cost of level-0 = n
- Cost of level-1 = n/2 + n/2 = n
- Cost of level-2 = n/4 + n/4 + n/4 + n/4 = n and so on.

**Step-03:**

Determine total number of levels in the recursion tree-

- Size of sub-problem at level-0 = n/2
^{0} - Size of sub-problem at level-1 = n/2
^{1} - Size of sub-problem at level-2 = n/2
^{2}

Continuing in similar manner, we have-

Size of sub-problem at level-i = n/2^{i}

Suppose at level-x (last level), size of sub-problem becomes 1. Then-

n / 2^{x} = 1

2^{x} = n

Taking log on both sides, we get-

xlog2 = logn

x = log_{2}n

∴ Total number of levels in the recursion tree = log_{2}n + 1

**Step-04:**

Determine number of nodes in the last level-

- Level-0 has 2
^{0}nodes i.e. 1 node - Level-1 has 2
^{1}nodes i.e. 2 nodes - Level-2 has 2
^{2}nodes i.e. 4 nodes

Continuing in similar manner, we have-

Level-log_{2}n has 2^{log2n} nodes i.e. n nodes

**Step-05:**

Determine cost of last level-

Cost of last level = n x T(1) = θ(n)

**Step-06:**

Add costs of all the levels of the recursion tree and simplify the expression so obtained in terms of asymptotic notation-

= n x log_{2}n + θ (n)

= nlog_{2}n + θ (n)

= **θ (nlog _{2}n)**

**Problem-02:**

Solve the following recurrence relation using recursion tree method-

T(n) = T(n/5) + T(4n/5) + n

**Solution-**

**Step-01:**

Draw a recursion tree based on the given recurrence relation.

The given recurrence relation shows-

- A problem of size n will get divided into 2 sub-problems- one of size n/5 and another of size 4n/5.
- Then, sub-problem of size n/5 will get divided into 2 sub-problems- one of size n/5
^{2}and another of size 4n/5^{2}. - On the other side, sub-problem of size 4n/5 will get divided into 2 sub-problems- one of size 4n/5
^{2}and another of size 4^{2}n/5^{2 }and so on. - At the bottom most layer, the size of sub-problems will reduce to 1.

This is illustrated through following recursion tree-

The given recurrence relation shows-

- The cost of dividing a problem of size n into its 2 sub-problems and then combining its solution is n.
- The cost of dividing a problem of size n/5 into its 2 sub-problems and then combining its solution is n/5.
- The cost of dividing a problem of size 4n/5 into its 2 sub-problems and then combining its solution is 4n/5 and so on.

This is illustrated through following recursion tree where each node represents the cost of the corresponding sub-problem-

**Step-02:**

Determine cost of each level-

- Cost of level-0 = n
- Cost of level-1 = n/5 + 4n/5 = n
- Cost of level-2 = n/5
^{2}+ 4n/5^{2}+ 4n/5^{2}+ 4^{2}n/5^{2}= n

**Step-03:**

Determine total number of levels in the recursion tree. We will consider the rightmost sub tree as it goes down to the deepest level-

- Size of sub-problem at level-0 = (4/5)
^{0}n - Size of sub-problem at level-1 =(4/5)
^{1}n - Size of sub-problem at level-2 =(4/5)
^{2}n

Continuing in similar manner, we have-

Size of sub-problem at level-i = (4/5)^{i}n

Suppose at level-x (last level), size of sub-problem becomes 1. Then-

(4/5)^{x}n = 1

(4/5)^{x} = 1/n

Taking log on both sides, we get-

xlog(4/5) = log(1/n)

x = log_{5/4}n

∴ Total number of levels in the recursion tree = log_{5/4}n + 1

**Step-04:**

Determine number of nodes in the last level-

- Level-0 has 2
^{0}nodes i.e. 1 node - Level-1 has 2
^{1}nodes i.e. 2 nodes - Level-2 has 2
^{2}nodes i.e. 4 nodes

Continuing in similar manner, we have-

Level-log_{5/4}n has 2^{log5/4n} nodes

**Step-05:**

Determine cost of last level-

Cost of last level = 2^{log5/4n} x T(1) = θ(2^{log5/4n}) = θ(n^{log5/42})

**Step-06:**

Add costs of all the levels of the recursion tree and simplify the expression so obtained in terms of asymptotic notation-

= nlog_{5/4}n + θ(n^{log5/42})

**= θ(nlog _{5/4}n)**

**Problem-03:**

Solve the following recurrence relation using recursion tree method-

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

**Solution-**

**Step-01:**

Draw a recursion tree based on the given recurrence relation-

(Here, we have directly drawn a recursion tree representing the cost of sub problems)

**Step-02:**

Determine cost of each level-

- Cost of level-0 = cn
^{2} - Cost of level-1 = c(n/4)
^{2}+ c(n/4)^{2 }+ c(n/4)^{2}= (3/16)cn^{2} - Cost of level-2 = c(n/16)
^{2}x 9 = (9/16^{2})cn^{2}

**Step-03:**

Determine total number of levels in the recursion tree-

- Size of sub-problem at level-0 = n/4
^{0} - Size of sub-problem at level-1 = n/4
^{1} - Size of sub-problem at level-2 = n/4
^{2}

Continuing in similar manner, we have-

Size of sub-problem at level-i = n/4^{i}

Suppose at level-x (last level), size of sub-problem becomes 1. Then-

n/4^{x} = 1

4^{x} = n

Taking log on both sides, we get-

xlog4 = logn

x = log_{4}n

∴ Total number of levels in the recursion tree = log_{4}n + 1

**Step-04:**

Determine number of nodes in the last level-

- Level-0 has 3
^{0}nodes i.e. 1 node - Level-1 has 3
^{1}nodes i.e. 3 nodes - Level-2 has 3
^{2}nodes i.e. 9 nodes

Continuing in similar manner, we have-

Level-log_{4}n has 3^{log4n} nodes i.e. n^{log43} nodes

**Step-05:**

Determine cost of last level-

Cost of last level = n^{log43} x T(1) = θ(n^{log43})

**Step-06:**

Add costs of all the levels of the recursion tree and simplify the expression so obtained in terms of asymptotic notation-

= cn^{2} { 1 + (3/16) + (3/16)^{2} + ……… } + θ(n^{log43})

Now, { 1 + (3/16) + (3/16)^{2} + ……… } forms an infinite Geometric progression.

On solving, we get-

= (16/13)cn^{2} { 1 – (3/16)^{log4n} } + θ(n^{log43})

= (16/13)cn^{2} – (16/13)cn^{2} (3/16)^{log4n} + θ(n^{log43})

= **O(n ^{2})**

Get more notes and other study material of **Design and Analysis of Algorithms (DAA)**.

Watch video lectures by visiting our YouTube channel **LearnVidFun**.