The master method - why can't it solve T(n) = T(n/2) + n^2/logn?
The master method - why can't it solve T(n) = 4*T(n/2) + (n^2)/logn?
I realize it can solve recurrences of type T(n) = aT(n/b) + f(n)
On MIT OCW they mentioned that it couldn't solve the above recurrence though. Can someone provide an explanation as to why?
Answer
Answer for T(n/2) + (n^2)/logn:
Case 1 does not apply because f(n) != O(n^-e) for any positive e.
Case 2 does not apply because f(n) != Θ(log^k(n)) for any k >= 0
Case 3 does not apply,
f(n) = Ω(n^e) for e = 1, BUT
a*f(n/b) <= c*f(n) for no c<1 (works out that c >= 2)
So we can't apply any case. Beyond this I'm no good really - and again I'm not 100% on this answer.
The following was prior to this edit, and assumed the question was with regards to T(n) = T(n/2) + n^(2logn) I'm fairly sure that it is case 3 of the theorum.
Case 1 does not apply because f(n) != O(n^-e) for any positive e.
Case 2 does not apply because f(n) != Θ(log^k(n)) for any k >= 0
Case 3 does apply,
a*f(n/b) <= c*f(n) for some c<1 (works out that c >= 0.5)
and f(n) = Ω(n^e) for e = 1
I may be wrong so check it and let me know!