Find the smallest integer $n$ such that $5x^5 + (\log x)^{5^5} \in O(x^n).$ Find the smallest integer $n$ such that $5x^5 + (\log_2 x)^{5^5}$ is $O(x^n).$
I know that $5x^5$ is $O(x^5),$ and that $\log_2 x$ is $O(x).$ Since $5^5=3,125$ and $\log_2 x$ is $O(x),$ I know that I can use a Theorem to get
$$
\begin{aligned}
(\log_2 x)^{5^5} &= \underbrace{\log_2 x\cdot\log_2 x\cdots\log_2 x}_{3,125\text{ times}}\\ 
&{}\\
&= O(\underbrace{x\cdot x\cdots x}_{3,125\text{ times}})\\ 
&{}\\
&= O(x^{3,125}).
\end{aligned}
$$
Then I can use another theorem to get
$$
5x^5 + (\log_2x)^{5^5} = O(\max(|x^5|,|x^{3,125}|) = O(x^{3,125}).
$$
The issue that I'm having is showing that $3,125$ is the smallest $n.$ I'm pretty sure that it's not the smallest $n$, but how do I find the smallest one if it isn't? If it is the smallest one, how do I prove it?
 A: The reason you are having trouble showing that $3125$ is the smallest such $n$ is because it actually isn't the smallest such $n$.
Intuitively, any constant power of $\log x$ grows slower than any constant power of $x$. Can you show that $\log^m x = O(x^a)$ for any $m > 0$ and any $a > 0$? Alternatively, do you already have a theorem that shows this?
Once you do this, then $\log^{3125} x = O(x)$, and the rest is easy.
A: $\lim_{x\to\infty}\frac{\log(x)^{625}}{x} = 0$
(just imagine when $x=10^{1,000,000}$)
Thus, $5x^5 + ((\log(x))^{5^5} \in \mathcal{O}(x^5)$
A: The following shows that $(\log x)^{5^5} \in O(x)$: For positive $y$ we have
$$
\begin{aligned}
y &< 2^y &&\text{can prove by induction}\\
\sqrt[5^5]{x} &< 2^{\sqrt[5^5]{x}} &&\text{set }y = \sqrt[5^5]{x}\text{ for positive } x\\
\log_2\left(\sqrt[5^5]{x}\right) &<\log_2\left(2^{\sqrt[5^5]{x}}\right) &&\text{take $\log_2$ of both sides}\\
\frac{1}{5^5}\log_2x &< \sqrt[5^5]{x} &&\text{simplify}\\
\left(\frac{1}{5^5}\log_2x\right)^{5^5} &< \left(\sqrt[5^5]{x}\right)^{5^5} &&\text{raise to the }5^5\text{ power}\\
\left(\frac{1}{5^5}\right)^{5^5}(\log_2x)^{5^5}&< x\\
(\log_2x)^{5^5} &< (5^5)^{5^5}x &&\text{multiply by}(5^5)^{5^5}.
\end{aligned}
$$
Hence, $(\log_2x)^{5^5}\in O(x).$
Combining this with $5x^5\in O(x^5)$, we have
$$
5x^5+(\log_2x)^{5^5}\in O(\max(|x^5|,|x|)) = O(x^5).
$$
