Which function grows faster asymptotically

Question

I have two functions which are $f(n) = \lg(n)$ and $g(n) = \lg^2(n)$, and I have to state which one grows at a faster rate. I took the derivatives of both and got $f'(n) = \dfrac 1n$ and $g'(n) = 2\dfrac{\lg(n)}n$. I plugged in values for both derivatives and see that $f'(n)\to 0$ as $n \to \infty$ and $g'(n)\to0$ as $n\to \infty$. However, I'm not sure if that means that they are growing at the same rate. Do I use L'Hoptial's rule to prove that or does the work that I've done prove that.

Answer 1

Note that $g(n)=\lg(n) f(n)$ and for large $n, \lg (n) \gt 1$ and goes to $\infty$. You don't need derivatives at all.

Answer 2

In addition to Ross' answer, there are several methods you can use to determine whether $f(n) = \lg(n)$ grows faster or slower than $g(n) = \lg^2(n)$, the simplest being graphically. The plot clearly shows that $g(n)$ grows much faster than $f(n)$ as $n\to\infty$.

You could also use the definition of $\mathcal O$ to find out if $f(n)\in\mathcal O(g(n))$. The definition states that

$f(n)\in\mathcal O(g(n))$ if $\exists n_0, c > 0$ s.t. $\forall n > n_0, f(n) \le cg(n)$.

Let's check if inequality is satisfied.

$$\begin{align}f(n) &\le c g(n) \\ \lg(n)&\le c\lg^2(n) \\ \implies \dfrac 1{\lg(n)}&\le c\end{align}$$

Set $n_0 = 2\implies c \ge 1$. You can verify that $\forall n > n_0 = 2$, $c\ge\dfrac1{\lg(n)}$. And, therefore, $f(n) = \lg(n)\in\mathcal O(g(n)) = \mathcal O\left(\lg^2(n)\right)$.

Finally, you can also use limits to determine if $f(n)\in\mathcal O(g(n))$. This is true if $$0 \le \lim_{n\to\infty}\dfrac{f(n)}{g(n)} < \infty.$$ I leave this for you as an exercise.