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$ Aug 26, 2020 at 22:04
  • 1
    $\begingroup$ Ah thanks @Aryadeva. I don't know how i flipped that around. $\endgroup$
    – sn3jd3r
    Aug 26, 2020 at 22:11
  • $\begingroup$ you're welcome ...... $\endgroup$ Aug 26, 2020 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, 2020 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, 2020 at 22:15

2 Answers 2

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$
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$ Aug 26, 2020 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$
    – alex
    Aug 26, 2020 at 22:01
  • $\begingroup$ @SeverinSchraven Yes sorry, now it is fixed! $\endgroup$
    – user
    Aug 26, 2020 at 22:11
  • $\begingroup$ @AlexandruDinu Thanks fixed! $\endgroup$
    – user
    Aug 26, 2020 at 22:12

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.