Recurrance Relation-Recursion Tree

Question

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

What is the solution of Above Given recurrence relation?

Give full method to solve this

Answer 1

This type of recurrence relation solve by recursion tree.

Note-

In the recursive tree

    i)Whenever at bigger level decreasing series came then  decreasing series is to constant.So answer is equal to its level.

              example-T(n)=T(n/6)+4n/6)

                                  T(n)=n((5/6)^0 +(5/6)^1+(5/6)^2+..........)

                                      O(n)

ii)Whenever at bigger level increasing came its complexity more than  O(nlogn)

       example-T(n)=T(n/5)+T(6n/5)

iii)if every level contain n time then complexity is O(nlogn) .

     example-T(n) = T(n/3)+T(2n/3)+n

Solution-

                             

Comments

Thanks, I got it now!

Answer 2

The above recurrence relation contain two recursive calls. This type of recurrence relations containing more than one recursive call is solved by recursive tree method.

Time complexity of above relation will be O(n log_3/2n).