How To Draw A Recursion Tree

The Recursion Tree Method is a way of solving recurrence relations. In this method, a recurrence relation is converted into recursive trees. Each node represents the cost incurred at various levels of recursion. To detect the total cost, costs of all levels are summed upwardly.

Steps to solve recurrence relation using recursion tree method:

Draw a recursive tree for given recurrence relation
Calculate the cost at each level and count the total no of levels in the recursion tree.
Count the total number of nodes in the terminal level and summate the cost of the last level
Sum up the cost of all the levels in the recursive tree

Allow us see how to solve these recurrence relations with the help of some examples:

Question ane: T(n) = 2T(n/2) + c

Solution:

Step 1: Draw a recursive tree

Recursion Tree

Footstep 2: Calculate the work done or cost at each level and count total no of levels in recursion tree

Recursive Tree with each level cost

Count the full number of levels –

Choose the longest path from root node to leafage node

due north/2⁰ -→ n/2¹ -→ north/2ⁱⁱ -→ ……… -→ north/2^k

Size of problem at last level = n/2^k

At last level size of problem becomes 1

n/2^yard = 1

ii^thou = north

k = log₂(northward)

Total no of levels in recursive tree = k +1 = log_ii(n) + one

Step iii: Count total number of nodes in the last level and summate cost of last level

No. of nodes at level 0 = 2⁰ = 1

No. of nodes at level 1 = 2ⁱ = 2

………………………………………………………

No. of nodes at level log_ii(n) = 2^log _² ^{(due north)} = n^log _² ⁽²⁾= due north

Cost of sub problems at level log_two(n) (terminal level) = nxT(1) = nx1 = n

Step 4: Sum upward the toll all the levels in recursive tree

T(n) = c + 2c + 4c + —- + (no. of levels-1) times + concluding level cost

= c + 2c + 4c + —- + log₂(northward) times + Θ(northward)

= c(ane + 2 + 4 + —- + log₂(n) times) + Θ(n)

1 + two + 4 + —– + log₂(n) times –> ii⁰ + twoⁱ + two² + —– + log2(n) times –> Geometric Progression(Yard.P.)

= c(n) + Θ(due north)

Thus, T(northward) = Θ(n)

Question 2: T(n) = T(n/x) + T(9n/ten) + n

Solution:

Step one: Draw a recursive tree

Recursive Tree

Step 2: Calculate the work washed or price at each level and count total no of levels in recursion tree

Recursion Tree with each level cost

Count the total number of levels –

Choose the longest path from root node to leaf node

(9/ten)⁰n –> (9/x)¹n –> (nine/x)²n –> ……… –> (nine/10)¹⁰⁰⁰n

Size of trouble at last level = (9/10)^mn

At last level size of problem becomes 1

(9/x)^kn = 1

(9/10)¹⁰⁰⁰ = 1/due north

k = log_10/9(n)

Total no of levels in recursive tree = k +one = log_10/nine(n) + one

Pace 3: Count full number of nodes in the last level and calculate price of final level

No. of nodes at level 0 = ii⁰ = 1

No. of nodes at level one = ii¹ = 2

………………………………………………………

No. of nodes at level log_10/9(n) = ii^log _^10/9 ⁽ⁿ⁾ = n^log _^10/ix ⁽²⁾

Cost of sub problems at level log2(n) (last level) = n^log _^10/9 ⁽²⁾ x T(1) = northward^log _^10/9 ⁽²⁾ 10 1 = n^log _^10/9 ⁽²⁾

Step iv: Sum upwards the toll all the levels in recursive tree

T(n) = n + n + due north + —- + (no. of levels – 1) times + concluding level toll

= n + n + n + —- + log_x/9(n) times + Θ(north^log _^ten/9 ⁽²⁾)

= nlog_10/9(due north) + Θ(n^log _^x/ix ⁽²⁾)