Is $n\ \log_2\left(n\right)\ ∈\ Ω\left(n^{1.001}\right)$? 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
 A: 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.
A: 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
$.
A: 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).$$
