I need to prove that one function, say $n$ grows faster than say, $\sqrt{n}$?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Use Principle of mathematical induction. $\endgroup$– user98061Oct 1, 2013 at 16:58
-
$\begingroup$ 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. $\endgroup$– Dan RustOct 1, 2013 at 18:41
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
answered Oct 1, 2013 at 16:15
$\begingroup$
$\endgroup$
6
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$.
-
-
$\begingroup$ 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}}$. $\endgroup$ Oct 1, 2013 at 16:32
-
-
$\begingroup$ Also, what about $f$ and $g$ where $f'(n) > g'(n)$, but there exists $m > n$ such that $f'(m) < g'(m)$? $\endgroup$ Oct 1, 2013 at 16:44
-
$\begingroup$ 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. $\endgroup$ Oct 1, 2013 at 16:45