Ingrid Morstrad
Ingrid Morstrad

Reputation: 187

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?

Upvotes: 2

Views: 9750

Answers (4)

Vinit
Vinit

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

Ashutosh Kumar
Ashutosh Kumar

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

Avinash Kadimisetty
Avinash Kadimisetty

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

user798182
user798182

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

Related Questions