# Why is $\log_{2}n = O(n^{0.00001})$? [duplicate]

Why is $$\log_{2}n = O(n^{0.00001})$$ true?

This is obvious to me when the exponent is $$> 1$$ but i'm having trouble understanding the cases where the exponent is very close to $$0$$. I would have to find some constants $$c$$ and $$n_0$$ where $$\log_{2}n \le cn^{0.00001}$$ for all $$n \gt n_0$$.

Where I'm stumped is that $$n^{0.00001} \approx 1$$ and $$\log_{2}n$$ approaches infinity as $$n$$ gets larger. It feels like regardless of whatever $$c$$ and $$n_0$$ I choose, if $$n$$ was large enough, I could show that $$\log_{2}n \ge c$$.

• Try what happens if n = 2^10,000,000. Now n^0.00001 = 2^100, while log n = 10,000,000. 2^100 is a lot larger than 10,000,000. – gnasher729 Mar 14 '20 at 8:09

## 1 Answer

$$n^{0.00001}$$ is not approximately $$1$$. $$n^{0.00001}$$ goes to infinity as $$n \to \infty$$.

You can see that $$\log_2 n = o( n^{0.00001} )$$ by taking the limit of their ratio: $$\lim_{n \to \infty} \frac{\log_2 n}{n^{0.00001}} = \lim_{n \to \infty} \frac{n^{-1}}{0.00001 \cdot n^{0.00001} \cdot n^{-1}} = \lim_{n \to \infty} \frac{100000}{n^{0.00001}} = 0.$$

This tells you that you can pick any value of $$c>0$$, for example $$c=1$$. Now you just need a value $$n_0$$ such that $$n^{0.00001} - \log_2 n \ge 0 \; \forall n \ge n_0$$.

The derivative of $$n^{0.00001} - \log_2 n$$ is $$n^{-1}( 0.00001 \cdot n^{0.00001} - 1)$$ which is non-negative as soon as $$n^{0.00001} \ge 100000$$, i.e., for $$n \ge 10^{5 \cdot 10^5}$$.

You can then pick any value of $$n_0$$ such that $$(n_0)^{0.00001} - \log_2 n_0$$ is non-negative and $$n_0 \ge 10^{5 \cdot 10^5}$$. For example $$n_0 = 2^{10^{7}}$$. Indeed:

• $$(n_0)^{0.00001} = 2^{100} = 1024^{10} > 1000^{10} = 10^{30} > 10^7 = \log_2 n_0$$; and
• $$n_0 = 1024^{10^6} > 1000^{10^6} = 10^{3 \cdot 10^6} > 10^{5 \cdot 10^5}$$.