<s>[INST] 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?
 [/INST] 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).
$$
</s>