Proving $\log^3n=O(n)$

Question

I am a little confused as in how to prove this:

$$\log^3n=O(n)$$

Any tips/hints on how to proceed? I have tried taking logarithms or exponentiating both sides but nothing seems to help.

EDIT: By $\log^3n$, I mean $(\log n)^3$.

Answer 1

Hint:

If the function $\frac{\log^3{n}}{n}$ is bounded then $\log^3{n}=O(n)$.

Basically just take $$\lim_{n \to \infty} \frac{\log^3{n}}{n}$$ and you'll see what I mean.

Answer 2

(1) $\lim_{x \to \infty} \log x=\infty$ because for positive integer $ n$ , if $ x \ge 2^n $ then $ \log x \ge n\log 2$......(2) If $ x>1$ then $\log x >0$ so $$x=e^{\log x}=\sum_{j=0}^{\infty} \frac {(\log x)^j} {j!}>\frac{(\log x)^4} { 4!} \implies$$ $$ \lim_{x \to \infty} \frac {x} {(\log x)^3} \ge \lim_{n \to \infty} \frac {1} {24} \log x=\infty.$$ Similarly, we have $(\log x )^k =O(x)$ for any $k>0$.

Answer 3

A more elementary proof without the power series: For ease of typing let $Y(x)= \log x$, and let $M(x) \in Z$ where $Y(x) \le M(x) <Y(x)+1$ .For $x>1$ we have $M(x)>0$ so $$ e^5 x =e^{5+Y(x)}>2^{5+Y(x)}> 2^{4+M(x)}=$$ $$=\sum_{j=0}^{4+M(x)} \binom {4+M(x)} {j}>\binom {4+M(x)} {4} >M(x)^4/4!\ge Y(x)^4/4!.$$ $$\text {Therefore }x>1 \implies x > Y(x)^4/(4! e^5)=(\log x)^4/(24 e^5).$$