Difference between solving T(n) = 2T(n/2) + n/log n and T(n) = 4T(n/2) + n/log n using Master Method
Solution 1
If you try to apply the master theorem to
T(n) = 2T(n/2) + n/log n
You consider a = 2, b = 2
which means logb(a) = 1
- Can you apply case 1?
0 < c < logb(a) = 1
. Isn/logn = O(n^c)
. No, becausen/logn
grow infinitely faster thann^c
- Can you apply case 2? No.
c = 1
You need to find some k > 0 such thatn/log n = Theta(n log^k n )
- Can you apply case 3 ?
c > 1
, isn/logn = Big Omega(n^c)
? No because it is not evenBig Omega(n)
If you try to apply the master theorem to
T(n) = 4T(n/2) + n/log n
You consider a = 4, b = 2
which means logb(a) = 2
Can you apply case 1?
c < logb(a) = 2
. isn/logn = O(n^0)
orn/logn = O(n^1)
. Yes indeedn/logn = O(n)
. Thus we haveT(n) = Theta(n^2)
note: Explanation about 0 < c <1, case 1
The case 1 is more about analytics.
f(x) = x/log(x) , g(x) = x^c , 0< c < 1
f(x) is O(g(x)) if f(x) < M g(x) after some x0, for some M finite, so
f(x) is O(g(x)) if f(x)/g(x) < M cause we know they are positive
This isnt true here We pose y = log x
f2(y) = e^y/y , g2(y) = e^cy , 0< c < 1
f2(y)/g2(y) = (e^y/y) / (e^cy) = e^(1-c)y / y , 0< c < 1
lim inf f2(y)/g2(y) = inf
lim inf f(x)/g(x) = inf
Solution 2
This is because in Q18 we have a = 4
and b = 2
, thus we get that n^{log(b,a)} = n^2
which has an exponent strictly bigger than the exponent of the polynomial part of n/log(n)
.
Vaibhav
Updated on June 05, 2022Comments
-
Vaibhav almost 2 years
I recently stumbled upon a resource where the 2T(n/2) + n/log n type of recurrences were declared unsolvable by MM.
I accepted it as a lemma, until today, when another resource proved to be a contradiction (in some sense).
As per the resource (link below): Q7 and Q18 in it are the rec. 1 and 2 respectively in the question whereby, the answer to Q7 says it can't be solved by giving the reason 'Polynomial difference b/w f(n) and n^(log a base b)'. On the contrary, answer 18 solves the second recurrence (in the question here) using case 1.
http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf
Can somebody please clear the confusion?
-
Vaibhav over 9 yearsSimone, so what is the story between 'strictly' (n^2) and 'seemingly' (n) bigger in contrast to 2T(n/2) (the first rec.)? f(n) = n/log n is O(n) and O(n^2)..
-
Vaibhav over 9 yearsUmNyobe, may be i'm also unclear about the case 1 then. Here's my understanding. Case 1 says that f(n) 'part' of the recurrence must be O(n^(log a base b - e)) where e is a constant > 0 So what's wrong with n/log n = O(n^(1-some c : 0<c<1)) ? So, may be not case 3 but can apply case 1 to both..
-
UmNyobe over 9 years
-
Vaibhav over 9 yearsMine goodness.. I thought the fraction has x divided by a function of x, viz. log x so it has got to be less than x.. So, what about your point # 3? It's not even big-omega (n^c).
-
UmNyobe over 9 yearssame as case 1. please do the math.
-
Vaibhav over 9 yearsNope! I didn't get why you say that n/log n grows 'infinitely' faster than n^c.. and then it is not even >= c. n^c.. (big-omega). I understand the explanation of 4T(n/2), n/log n being O(n^2) to fall in case 1 for "exponent strictly bigger than the exponent of the polynomial part of n/log(n)" from Simone's answer..
-
Vaibhav over 9 yearsI guess I get it now.. n/log n is not big-omega(n^c) because that case says f(n) should be big-omega(n^(log a base b + e)) : e > 0. It is because of this e.. right?
-
Vaibhav over 9 yearsUmNyobe, can you please confirm that hence, all rec. of the form T(n) = a T(n/a) + n/log n are not solvable by MM.. ?
-
UmNyobe over 9 yearslooking the way you stated seems more complicated than anything else. I used a proof by contradiction. n^c, c> 1 is big omega n. if f(n) is big omega n^c, then f is big omega n (big O and omega are transitive). Showing that n/log n is not even big omega of function
n
means it is not going to be big omega n^c, c > 1. You can also take one value of c (like 2) and show that it doesn work. And yesT(n) = a T(n/a) + n/log n
are not solvable by MM is the conclusion you can have.