##### How to find time complexity of such function which is not in form of masters Theorem?

How to find time complexity of such function which is not in form of masters Theorem?

T(N/3) + T(2N/3) + N

How to find time complexity of such function which is not in form of masters Theorem?

T(N/3) + T(2N/3) + N

See this:

https://math.stackexchange.com/questions/1112012/recursion-tree-tn-tn-3-...

Not able to understand.......

@abhisinu

See the recursion tree below,

In the (i) recursion tree,

The shortest path to a leaf occurs when we take the heavy branch each time. The height k is given by n(1\3)

^{k}<=1 meaning n<= 3^{k}or k>=log_{3}n.The longest path to a leaf occurs when we take the light branch each time.The height k is given by n(2\3)

^{k}<=1 meaning n<= (3/2)^{k}or k>=log_{3/2}n.So if we want to get the lower bound, we will take the shortest path. You know that there are k levels and cost at every level is n. (See 2nd recursion tree).

Hence total cost = n * k = n * log

_{3}nTime complexity = omege (n log

_{3}n).Please let me know if you still have any doubt.

what is heavy and lighter branch?

I understand overall but doubt in heavy and lighter branch.

Thanks for best explaination

Heavy branch means the branching is going to end soon. Here it is becoming 1/3rd after every branch.

Lighter branch means the branching is not going to end soon. Here it becoming 2/3rd after every branch.(Lighter in comparison to the first one)