Recursion Tree

Recursion Tree Method :  Recursion tree method is a pictorial representation of an iteration method which is in the form of tree ,where at each level nodes are explained.
It is used  to keep track of the size of the remaining arguments in the recurrence.
A recursion tree is a tree where each node represents the cost of a certain recursive sub-problem.

➽ How to solve problem based on resursive tree
➤expanding the recurrence into a tree 
➤adding the cost at each level 
➤applying the substitution method 



Example :1
T(n) ={1  if n=1
          {2T(n/2)+n if n>1 
find time complexity.






























Example:2
Find the time complexity of  T(n) = T(n/3) + T(2n/3) +n  by The recursion tree method.



  Example:3

Find the time complexity of  T(n) = 2T(n/2) + n²       by The recursion tree method.

         

   The Time complexity should be O(n^2)



Do your self (By The recursion tree method)?

Q.1  T(n)=3T(n/2)+n

Q2. T(n)=4T(n/2)+n^2

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

Q4. T(n)=16T(n/4)+n

Q5.  T(n)=4T(n/2)+logn

Q6.  T(n)=3T(n/4)+nlogn

Q7.  T(n)=4T(n/2)+n/logn

Q8. T(n)=16T(n/4)+n!

Q9. T(n)=3T(n/3)+√n

Q10. T(n)=√2T(n/√2)+logn

Answers:

Q1. Ө(n^log3)

Q2. Ө(n^2 logn)

Q3. Ө(n^2)

Q4. Ө(n^2)

Q5. Ө(n^2)

Q6. Ө(nlogn)

Q7. Ө(n^2)

Q8. Ө(n!)

Q9. Ө(n)

Q10. Ө(√n)