Solving by Masters theorem and recursion tree gives different answers

768 Views Asked by At

Suppose we have been given a recurrence relation T(n) = 2T(n/3) + n. And need to find the time complexity. My problem is why I am getting different answers by master theorem and using recursion tree method.

By Master Theorem for equation T(n) = aT(n/b) + O(nklogpn)

Here a=2,b=3,p=0,k=1 and as a < bk here i.e 2 < 31 by masters theorem it gives us T(n) = O(n) time complexity.

Here is my recursion tree method

enter image description here

And at the end I seriously don't know what did I found out. It looks something like O(n.2logn).

  1. Surely its not the answer and I have messed it up. But I don't get where I am wrong? What is right approach?

  2. Also I wanted to ask if recurrence relations T(n) = 2T(n/3) + n and T(n) = 2T(n/3) + C are both same? where C is a constant in 2nd equation.

0

There are 0 best solutions below