1
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ $f'(n)$ is not correct. Check the derivative again.$f'=\dfrac {2 \log n }{n}$ $\endgroup$ – Aryadeva Aug 26 '20 at 22:04
  • 1
    $\begingroup$ Ah thanks @Aryadeva. I don't know how i flipped that around. $\endgroup$ – sn3jd3r Aug 26 '20 at 22:11
  • $\begingroup$ you're welcome ...... $\endgroup$ – Aryadeva Aug 26 '20 at 22:11
  • $\begingroup$ @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? $\endgroup$ – DUO Labs Aug 26 '20 at 22:13
  • $\begingroup$ @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))$ $\endgroup$ – sn3jd3r Aug 26 '20 at 22:15
0
$\begingroup$

We have that

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

$\endgroup$
4
  • 3
    $\begingroup$ I am a bit confused by your last line. If it is $o(n)$, then it is also $O(n)$, isn't it? $\endgroup$ – Severin Schraven Aug 26 '20 at 21:58
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Alexandru Dinu Aug 26 '20 at 22:01
  • $\begingroup$ @SeverinSchraven Yes sorry, now it is fixed! $\endgroup$ – user Aug 26 '20 at 22:11
  • $\begingroup$ @AlexandruDinu Thanks fixed! $\endgroup$ – user Aug 26 '20 at 22:12
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.