Prove that Big O (lg n) is a subset of Big O(sqrt(n))...

Question

Prove that Big O (lg n) is a subset of Big O(sqrt(n)) and exists an element x in set Big O(sqrt(n)) that is not in Big O(lg n). This is a home work question and I have no clue where to start. Do I use induction? or other types of proofs.

Answer 1

Hint: It suffices to show that there is a constant $C$ for which $\lg{n} \le C \sqrt{n}$ for all $n$ sufficiently large (why?). This can be done using the fact that

$$\lim_{n \to \infty} \frac{\lg{n}}{\sqrt{n}} = 0$$

since this implies that the quantity $\frac{\lg{n}}{\sqrt{n}}$ is bounded for large $n$; just let $C$ be this bound.

In order to prove the original statement, we use L'Hopital's rule to conclude that

$$\lim_{n \to \infty} \frac{\lg{n}}{\sqrt{n}} = \lim_{n \to \infty} \frac{1/(n \ln{2})}{n^{-1/2}/2} = \frac{2}{\ln{2}} \lim_{n \to \infty} \frac{\sqrt{n}}{n} = \frac{2}{\ln{2}} \lim_{n \to \infty} \frac{1}{\sqrt{n}} = 0$$

as desired.