It is obvious that $n\log n=\omega (n)$. But does this necessarily mean that $\exists \epsilon>0$ such that $n\log n=\Omega (n^{1+\epsilon})$? My intuition says yes, but I'm not sure what $\epsilon$ should be.
Asked
Active
Viewed 669 times
3
-
1If there were such an $\epsilon$, then you could divide both sides of the equation by $n$. What would you be left with? – Antonio Vargas Apr 13 '18 at 11:36
-
For all sufficiently large $n$ we'd have $\log n>c\cdot n^{\epsilon}$ for some constant $c$. Is there a reason why this cannot be true? – H.Rappeport Apr 13 '18 at 11:39
-
2If it's still not clear, divide that inequality by $n^\epsilon$. Do you believe that there is a positive $c$ such that $\frac{\log n}{n^\epsilon} > c$? Perhaps computing the limit of the left-hand side (hint: L'Hopital's rule) would help. – Antonio Vargas Apr 13 '18 at 11:43
-
Clear. Thank you for the explanation – H.Rappeport Apr 13 '18 at 11:46
-
Consider writing an Answer to your own question below. I'd be happy to upvote it. – Antonio Vargas Apr 13 '18 at 11:47
1 Answers
2
Answer (Thanks to Antonio Vargas): No such $\epsilon$ exists
Proof: Suppose, for the sake of contradiction, that $\exists \epsilon>0$ with $$n\log n=\Omega (n^{1+\epsilon})$$. This would imply that for all sufficiently large $n$ we'd have $$\frac{\log n}{n^\epsilon} > c$$ for some constant $c>0$. However, $$\lim_{n\rightarrow\infty}\frac{\log n}{n^{\epsilon}}\overbrace{=}^{L'Hopital}\lim_{n\rightarrow\infty}\frac{\frac{1}{n}}{\epsilon n^{\epsilon-1}}=\lim_{n\rightarrow\infty}\frac{1}{\epsilon n^{\epsilon}}\xrightarrow[n\rightarrow\infty]{}0$$ So no such constant exists
H.Rappeport
- 1,536