Find the smallest integer $n$ such that $5x^5 + (\log x)^{5^5} \in O(x^n).$

Question

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?

Answer 1

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.

Answer 2

$\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)$

Answer 3

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). $$