Solve recurrence relation by master theorem

Question

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

T(n) = 27T(n/3) + Q(n³log n)

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

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

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

Isn't it case 2 with a=27, b=3, & k = 1 with f(n) = theta(n log a to base b * log to power k n)? And thus t(n) is what you have? — another.anon.coward
@another.anon.coward: thanks, for your notable comment, but still i have little bit confusion 1: How we will decide which case of master theorem we will use, I read corman in which it was mentioned that for choosing case you have to first compute n^log a base b and comapre it with given f(n) if f(n)< then go for case 1 and f(n) = then go for 2nd and if f(n)> then go for 3rd case, I used here same concept to identify which case i shuld choose, so i came up with 3rd case, So how shuld i approch i mean go for selection of master theorem case.please sugest me something in Answer. — Nishant Kumar
I suggested it in the comment, because right now I am quite rusty with this topic :(, hoping someone better will come along & explain better. I think in this case it is pretty straight forward. You look at f(n) here, it is of the form n^p*log n (where p is log a to base b). Of the three case, the second case deals with the f(n) which has a log^k n factor. Thus you proceed to compute a & b for p. In other 2 cases f(n) has no log n factor — another.anon.coward
@another.anon.coward: Many many thanks two you, for your very precise and short answer. once again thanks. — Nishant Kumar

sukunrt sukunrt · Accepted Answer · 2012-01-27T19:10:29

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).

Solve recurrence relation by master theorem

1 Answers