Reputation: 187
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?
Upvotes: 2
Views: 9750
Reputation: 1
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
Upvotes: 0
Reputation: 1
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.
Upvotes: 0
Reputation: 143
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.
Upvotes: 0
Reputation:
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!
Upvotes: 2