Is $n^{0.01}$ Big Omega or Big O of $\log(n)$

Question

I was graphing $n^{0.01}$ for huge values of $n$ and noticed this function grows incredibly slow, much slower then $\log(n)$ it appeared from the graph. So my initial thought was that

$$n^{0.01}\in\mathcal O(\log(n))$$

$$\log^x(n)\in \mathcal O(n^y)$$

for any fixed constant $x > 0$ and $y > 0$, which made me think my initial thought was wrong.

Answer 1

It is enough to take the limit $\frac{n^{\alpha}}{\log n}$ with $\alpha >0$ to see that it tends to infinity and hence we get a stronger relation: $n^{\alpha} = \omega (\log n)$. In other words, the ratio is not bounded above by any constant.

Answer 2

How about this: Let $x_1 = 10^{1000}$ and $x_2 = 10^{2000}$. Then, assuming $\log$ is the base-10 logarithm,

$$\log(x_1) = 1000 \quad\text{and}\quad \log(x_2) = 2000.$$

From $x_1$ to $x_2$, $\log(x)$ increases by $1000$. However, $x_1^{0.01} = 10^{10}$ and $x_2^{0.01} = 10^{20}$. The difference between $10^{10}$ and $10^{20}$ is clearly greater than $2000$. So, at least here, we can see $n^{0.01}$ growing faster than $\log$.

Answer 3

To show that $\lim_{n\to\infty} \frac{n^a}{\log n}=\infty$ you can apply L'Hopital.

$$\lim_{n\to\infty}\frac{n^a}{\log n}=\lim_{n_\infty}\frac{a\cdot n^{a-1}}{\frac{1}{n}}=\lim_{n\to\infty}a\cdot n^a=\infty\ (\because a>0)$$