-2

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

pratnala
  • 99
  • 3
    Start with the definition: $f(n) = O(g(n))$ for $n\to\infty$ if there exist a constant $C$ such that $f(n) \leq Cg(n)$ for all sufficiently large $n$. In this case it becomes $\log^3(n) \leq Cn$ or $\frac{\log^3(n)}{n} \leq C$. There are several ways to continue from here. For example you can start by computing the limit $\lim_{n\to\infty}\frac{\log^3(n)}{n}$. – Winther Sep 24 '15 at 00:45
  • Well, $(\log x)^3 < x$ if $x > 100$, by looking at the graphs... – lhf Sep 24 '15 at 01:41

3 Answers3

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.

Aleksandar
  • 1,771
1

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

DanielWainfleet
  • 57,985
0

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

DanielWainfleet
  • 57,985