How do I prove that a function grows faster than another? [closed]

$\begingroup$

I need to prove that one function, say $n$ grows faster than say, $\sqrt{n}$?

$\endgroup$ 2

2 Answers

$\begingroup$

There are many ways. One, which works here, is to divide $\frac n{\sqrt n}=\sqrt n$ and show that goes to infinity as $n$ gets large.
Often in these problems "grows faster" means at least that the difference grows without bound, sometimes that the ratio grows without bound. You need to be clear which you want. In this example, we meet both requirements.

$\endgroup$ $\begingroup$

I would compute the first Derivation $f(n) = n$ and $g(n) = \sqrt{n}$. If $f^\prime(n) > g^\prime(n)$ then $f$ grows faster than $g$.

$\endgroup$ 6