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:

1. Draw a recursive tree for given recurrence relation
2. Calculate the cost at each level and count the total no of levels in the recursion tree.
3. Count the total number of nodes in the terminal level and summate the cost of the last level
4. 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 ₂ (2)} = 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)} = n^{log _10/ix (2)}

Cost of sub problems at level log2(n) (last level) = n^{log _10/9 (2)} x T(1) = northward^{log _10/9 (2)} 10 1 = n^{log _10/9 (2)}

• 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 (2)})

= nlog_10/9(due north) + Θ(n^{log _x/ix (2)})

Thus, T(n) = Θ(nlog _ten/9 (n))

Source: https://www.geeksforgeeks.org/how-to-solve-time-complexity-recurrence-relations-using-recursion-tree-method/

Posted by: lenoxnembee.blogspot.com

Share this post