Online doubt

Question

while solving this recursive equation:

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

i tried the master theorem ignoring the less long term T(n/3)

this gave me : T(n)=T(2n/3)+n; and it leads to O(n) Time complexity.

And doing with recursive tree  method it gave me   N(logN base 3/2)..

So what is wrong with master theorem approach?

Comments

Can you please let me the approach that you are using, How you are applying the master theorem on this?

Answer 1

https://gateoverflow.in/227589/self-doubt

 

Comments

Best solution @prince

Answer 2

The problem is ignoring the smaller term. You cannot ignore the smaller term like this because even though small it has an effect on the overall running of the function or relation. So whenever you encounter such problems, use recurrence tree method only.

Answer 3

The master theorem can be employed to solve recursive equations of the form

where a ≥ 1, b > 1, and f(n) is asymptotically positive.

The equation that you are trying to solve can't be solved effectively by using master theorem, Best to go with recursive tree method to get the optimal answer.