Behavior of $\log(x)^n$ when $x \rightarrow +\infty$ with respect to x?

Question

I am working with algorithmic complexity and I came up with a basic math question regarding the behavior of $\log(x)^n$ when $x \rightarrow +\infty$ with respect to x.

I would like to prove that if $\log(x) > 1$, then for any $n$ there is always a $\hat{x}$ such that $\log(x)^n < x$ when $x > \hat{x}$.

From an algorithmic complexity point of view it means that a $\mathcal{O}(\log(x)^n)$ algorithm is asymptotically better than a $\mathcal{O}(x)$ for any $n$.

Answer 1

You may try to apply the L'Hopital rule $n$ times: $$ \lim_{x \rightarrow \infty} \frac{(\ln x)^n}{x} = \lim_{x \rightarrow \infty} \frac{n(\ln x)^{n-1}}{x}=...= \lim_{x \rightarrow \infty} \frac{n!}{x} =0 $$

Answer 2

Let $y = \log x$ (I'm assuming thats the natural logarithm, but either way, you can replace $e$ with $2$ if needed). Then the question if $(\log x)^n \in \mathcal{O}(x)$ becomes whether $\lim_{x\rightarrow\infty} \frac{|y^n|}{|e^y|} = 0$. This can be further reframed as

$$ \lim_{y\rightarrow\infty} \frac{|y^n|}{|e^y|} = 0 $$ That's because when $x$ goes to infinity, $y$ also goes to infinity (because the logarithm with base > 1 is strictly increasing and unbounded.

Hope this is easier to finish now.