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. – Steven Jan 12 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. – mmafshari Jan 12 at 15:53
• See my answer.$\phantom{}$ – Steven Jan 12 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. – Steven Jan 12 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)$. – Steven Jan 12 at 16:42