The difference between the solution T (n) = 2T (n / 2) + n / log n and T (n) = 4T (n / 2) + n / log n using the Master method

Question

I recently came across a resource where 2T (n / 2) + n / log n repetition type was declared unresolvable MM.

I accepted this as a lemma, until today, when another resource turned out to be a contradiction (in a sense).

According to the resource (link below): Q7 and Q18 in it - rec. 1 and 2, respectively, in the question according to which the answer to Q7 says that it cannot be solved by indicating the reason “The polynomial difference is b / wf (n) and n ^ (log ab). On the contrary, answer 18 solves the second repeat (in this question) using case 1.

http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf

Can someone please clear the confusion?

Answer 1

If you try to apply the main 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 . Is n/logn = O(n^c) . No, because n/logn grows infinitely faster than n^c
• Can you apply case 2? No. c = 1 You need to find k> 0 so that n/log n = Theta(n log^kn )
• Can you apply case 3? c > 1 , n/logn = Big Omega(n^c) ? No, because it's not even Big Omega(n)

If you try to apply the main 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 . n/logn = O(n^0) or n/logn = O(n^1) . Yes, indeed, n/logn = O(n) . Thus, we have

   T(n) = Theta(n^2) 

Note: Explanation about 0 <c <1, case 1

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 is not true. We represent 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 

Answer 2

This is due to the fact that in Q18 we have a = 4 and b = 2 , therefore we get that n^{log(b,a)} = n^2 , whose exponent is exponentially greater than the exponent of the polynomial part n/log(n)