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?
On
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!
On
f(n)=(n^2)/logn and n^(log a/log b) . Compute the difference between the above two functions.
ratio= (n^2/log n)/(n^2)
The ratio turns out to be logarithmic. This recurrence relation falls in to the gap between case 2 and case 3. So Masters theorem is not applicable for this recurrence relation.
Masters theorem is applicable when the difference between the two functions stated above is polynomial.
On
its because in all the mentioned three cases you can't justify the positive asymptotic nature. which means when n->infinity n^2/lg(n) -> infinity, that simply implies n^e = w(lg(n)), Which can be paraphrased as "the function can not be contained" no upper bound exists for dividing and conquering procedures.
It seems to be the 3rd case as f(n) is greater but it should also satisfy the regularity condition (af(n/b)<=cf(n) for some c in(0,1)). Here the function is not satisfying the regularity condition so master method fails here