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

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

• Use Principle of mathematical induction.
– user98061
Oct 1, 2013 at 16:58
• Do you want to know show that "say" $n$ grows faster than "say" $\sqrt{n}$ or do you want to show that $n$ grows faster than $\sqrt{n}$? Only one of these is an acceptable question (and you should still add more details about your thoughts and attempts so that we can place your question in to context. Oct 1, 2013 at 18:41

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.
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$.
• In your example, $1 > \frac{1}{2\sqrt{n}}$, so $n$ is constantly growing at a rate of 1 whereas the other function is decreasing at a rate of $\frac{1}{2\sqrt{n}}$. Oct 1, 2013 at 16:32
• Also, what about $f$ and $g$ where $f'(n) > g'(n)$, but there exists $m > n$ such that $f'(m) < g'(m)$? Oct 1, 2013 at 16:44
• Maybe we should first discuss the meaning of grows faster. The first derivation shows how fast a function f grows at a fixed point $n$ (in your example it has always a 'growing factor' 1'). The function $g$ has a growing factor $\frac{1}{2 \sqrt{n}}$. If we now look at the 'growing factor' at the point $n = 0.5$. The $g$ grows faster then the function $f$: $1 < \frac{1}{2 \cdot 0.25} = 2$. But for $n = 2$ $f$ grows faster then $f$: $1 > \frac{1}{2}$. As you see the growing rate is only a local property. Oct 1, 2013 at 16:45