# How to prove $T(n) = 2T(n/2) + n/\log(n)$ can't be solved using the Master Theorem?

I have read (in this question) that this recursion can't be solved via Master Theorem. But I couldn't find exact and complete proof why the Master Theorem does not apply.

• There isn't much to prove.. you take the statement of the master Theorem and check whether the hypotheses needed to apply the theorem hold. Besides, this recurrence CAN be solved using the master theorem. Jan 12 '21 at 15:45
• @Steven OK. how should we do this? I have problem proving that n/log(n) is not polynomially smaller than n^log(2,2)! It seems clear that the two other statements of Master Theorem does not hold. Jan 12 '21 at 15:53
• See my answer.$\phantom{}$ Jan 12 '21 at 15:57

Your recursion can be written as: $$T(n) = aT(n/b) + f(n),$$ where $$a=b=2$$ and $$f(n) = n \log^{-1} n$$. Defining $$c_{crit} = \log_b a = 1$$ you can see that $$f(n) = \Theta( n^{c_{crit}} \log^k n)$$ for $$k=-1$$, therefore case 2b of the Master Theorem applies. The solution to the recurrence is therefore: $$T(n) = \Theta( n^{c_{crit}} \log \log n ) = \Theta( n \log \log n).$$
• Ohh, sorry. It was my mistake... somehow I had $n \log n$ in my mind... give me some time to write down why $1$ does not hold. Jan 12 '21 at 16:36
• Let $\epsilon>0$ be any constant. We want to compare $n^{\log_b a} = n$ with $\frac{n}{\log n}$. You can do so by taking the limit of their ratio: $\lim_{n \to \infty} \frac{n^{1-\epsilon}}{n / \log n} = \lim_{n \to \infty} \frac{n \log n}{n^{1+\epsilon}} = \lim_{n \to \infty} \frac{\log n}{n^{\epsilon}} = \lim_{n \to \infty} \frac{1/n}{\epsilon n^{\epsilon-1}} = \lim_{n \to \infty} \frac{1}{\epsilon n^\epsilon} = 0$. This shows that $\frac{n}{\log n} \in \omega(n)$ and hence $\frac{n}{\log n} \not\in O(n)$. Jan 12 '21 at 16:42