Solve recurrence relation by master theorem

3k views Asked by At

I am confused here which case of master theorem finding tight bound for this recurrence relation:

T(n) = 27T(n/3) + Q(n3log n)

Here is my solution:
f(n) = n3log n
a=27 b = 3 so

So we can see here that f(n) > n3
So this:

Case 3 will apply: correct me if I am wrong here.
Note: But it's answer is coming n3log2n which is coming by case 2 of Master Theorem. Which one should I apply?

1

There are 1 answers

0
sukunrt On

Check this:

http://en.wikipedia.org/wiki/Master_theorem#Case_2

And if you have the third edition of CLRS: Refer to question 4.6-3

You should be able to derive this following the Proof of the master theorem and then substituting the form of f(n).