Big O notation example. Why is $n^{1000} \in O(5^{\sqrt{n}})$? I thought that since $5^{\sqrt{1000}} < 1000^{1000}$ then it would be the otherway around. Could you please give me the mathematical derivation of this?
Thanks in advance
 A: You basically want to show that there exists some $n_o \in \mathbb{N}$, such that for all $n \geq n_o$, we have $n^{1000} \leq 5^{\sqrt{n}}$.
Taking log of both terms, we have, $1000\log(n)$ and $\sqrt{n} \log (5)$. At this step it is clear that $1000\log(n)$ will be dominated by $\sqrt{n} \log (5)$ for some $n_o$, since $\sqrt{n}$ is known to dominate over $\log(n)$ in the long run.
Then this implies the original inequality is true, and hence $n^{1000} \in \mathcal{O}(5^{\sqrt{n}})$.
Code:

sqrt(100000000000000000)*log(5)
ans =
5.0895e+08
log(100000000000000000)*1000
ans =
3.9144e+04

A: Take logs:
$$
1000\,\ln n \le \sqrt{n}\ln 5
$$
for large $n,$ as $\ln x=O(x^\alpha)$ for all $\alpha>0.$
A: With  d'Hospital it is easy to see that $x^{-1/2} \log x \to 0$ for $x \to \infty$
hence there is $N$ such that $n^{-1/2} \log n < \frac{\log 5}{1000}$ for $n >N$. This means
$n^{1000} < 5^{\sqrt n}$ for $n >N$. 
A: The $\mathcal O$ notation is only relevant for large $n$.
For $n=1000$ as in your post, there does not have to be an equality, since $1000$ is not large enough in this context.
For very large $n$, the inequality
$$
 n^{1000} < 5^{\sqrt n}
 $$
is indeed true.
