# Proof that $\log^2 n = O(n)$

I would like to prove that $$\log^2(n) = O(n)$$.

My attempt so far is:

Since $$\lim_{n \to \infty} \log^2(n) = \infty \text{ and } \lim_{n \to \infty} n = \infty$$ we get from L'Hôpital's rule that (let $$f(n) = \log^2n$$ and $$g(n) = n$$)

$$\lim _{n \rightarrow \infty} \frac{f(n)}{g(n)}=\lim _{n \rightarrow \infty} \frac{f^{\prime}(n)}{g^{\prime}(n)}=\lim _{n \rightarrow \infty} \frac{f^{\prime}(n)}{1} = \lim _{n \rightarrow \infty} \frac{n}{\log n} \cdot \frac{\ln 2}{2} = \infty$$

Hence $$\log^2 n = O(n)$$

Is this valid, and if not, where is it breaking?

EDIT: $$\lim _{n \rightarrow \infty} \frac{f(n)}{g(n)}=\lim _{n \rightarrow \infty} \frac{f^{\prime}(n)}{g^{\prime}(n)}=\lim _{n \rightarrow \infty} \frac{f^{\prime}(n)}{1} = \lim _{n \rightarrow \infty} \frac{2log n}{n} = 0$$

• $f'(n)$ is not correct. Check the derivative again.$f'=\dfrac {2 \log n }{n}$ – Aryadeva Aug 26 '20 at 22:04
• Ah thanks @Aryadeva. I don't know how i flipped that around. – sn3jd3r Aug 26 '20 at 22:11
• you're welcome ...... – Aryadeva Aug 26 '20 at 22:11
• @sn3jd3r I'm not sure you know what $O(n)$ means. It does not mean they have the same limit-- else $\ln(n)=O(n^3)$! Informally, it means that the dominating term is "roughly" $n$, for example $3n$ or $50n+\ln(n)$. Would you mind editing your question to clarify what you mean? – DUO Labs Aug 26 '20 at 22:13
• @DUO What? indeed ln(n) = O(n^3). This is standard. It does not mean that the dominating term is "roughly" $n$ in any definition i am aware of. Rather it means if there exists a positive real number $M$ and a real number $x_0$ such that $|f(x)| \leq M g(x) \quad$ for all $x \geq x_{0}$ then $f(x) = O(g(x))$ – sn3jd3r Aug 26 '20 at 22:15

$$\lim _{x \rightarrow \infty} \frac{\log^2 x}{x}\stackrel{H.R.}=\lim _{x \rightarrow \infty} \frac{2\log x}{x}\stackrel{H.R.}=\lim _{x \rightarrow \infty} \frac{2}{x}=0$$
therefore $$\log^2 n = O(n)$$ and $$\log^2 n = o(n)$$.
• I am a bit confused by your last line. If it is $o(n)$, then it is also $O(n)$, isn't it? – Severin Schraven Aug 26 '20 at 21:58
• There may be a typo in your response, as $f = o(g) \implies f = O(g)$. Moreover, if $\lim_{n \to \infty} f(n) / g(n) < \infty \implies f = O(g)$. – Alexandru Dinu Aug 26 '20 at 22:01
In light of the actual limit it is better (i.e. more accurate) to use asymptotic relations other than $$O(\cdot)$$. Since the limit, as @user showed, is $$0$$, the relationship is in fact $$f(n) = o(g(n))\\ g(n) = \omega(f(n))$$ Here $$f(n) = \log^2 n$$ and $$g(n) = n, \ \omega(f(n))$$ means that the ratio diverges (tends to infinity), $$o(\cdot)$$, as explained above, means that the ratio converges to $$0$$