Is $n\ \log_2\left(n\right)\ ∈\ Ω\left(n^{1.001}\right)$?

Question

I am trying to find out what class of function is this $n^{1.001}$ as I need to know whether it will smaller or equal to $n\ \log_2\left(n\right)$ . I am using master theorem where i am trying sigma = 0.001 for case 3

Answer 1

For any $\epsilon > 0$, $\log(n) = o(n^\epsilon)$. (The base of $\log$ doesn't matter, because logarithms with different bases are scalar multiples of each other.) The proof is by L'Hôpital: $$\lim_{n \to \infty} \frac{\log n}{n^{\epsilon}} = \lim_{n \to \infty} \frac{\frac{d}{dn} \log n}{\frac{d}{dn} n^\epsilon} = \lim_{n \to \infty} \frac{n^{-1}}{\epsilon n^{\epsilon - 1}} = \lim_{n \to \infty} \frac{1}{\epsilon n^\epsilon} = 0.$$ As an immediate consequence, $n \log n = o(n^{1.001})$, and the statement in your title is false.

Answer 2

Another proof that $\log(n) = o(n^c)$ for any $c > 0$.

If $n > 1$ and $0 < c < 1$, then

$\begin{array}\\ \log(n) &=\int_1^n \dfrac{dt}{t}\\ &<\int_1^n \dfrac{dt}{t^{1-c}}\\ &=\dfrac{t^c}{c}|_1^n\\ &=\dfrac{n^c-1}{c}\\ &<\dfrac{n^c}{c}\\ \end{array} $

Putting $c/2$ for $c$, $\log(n) \lt \dfrac{n^{c/2}}{c/2} $ so $\dfrac{\log(n)}{n^c} \lt \dfrac{2}{cn^{c/2}} \to 0 $.

Answer 3

The question is equivalent to

$$\log n\stackrel?\in\Omega(n^{0.001}),$$

and in fact the particular exponent is irrelevant. Indeed, using $n:=m^{1000a}$ with $a>0$, the proposition becomes

$$1000a\log m\stackrel?\in\Omega(m^{a}),$$ or just

$$\log m\stackrel?\in\Omega(m^{a})$$ and the logarithm grows slower than any positive power.

But we can take for granted that

$$\log m\notin\Omega(m).$$