# Intuition behind growth rate of some functions

This one really crushed my intuition. Let say a function $f$ grows faster than a function $g$ if $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$

Which of the following functions grows the fastest :

1. $2^{n/2}$

2. $3^{n/3}$

3. $5^{n/5}$

4. $1000^{1000/n}$

5. $10000^{10000/n}$

My bet would be on either function 1. or 5. but as it turns out, function 2. is growing the fastest.

After doing some calculations I was able to assure myself that that is really so. But my main doubt is still there. Why is this obvious? How can one intuitively explain this behavior?

-
Right, thanks! I will now change the function to a different one, to show my question more clearly. – Jernej Mar 9 '12 at 9:20
Hint: Think of the growth rate as the derivative of the function. – NoChance Mar 9 '12 at 9:25

First you should notice that 4. and 5. should be out of the question. This is because $\lim_{n\rightarrow\infty} 10000^{10000/n}=10000^{\lim_{n\rightarrow\infty}10000/n}=10000^0$. That basically means that the function will grow at a smaller and smaller rate.

Now we are left with 1., 2. and 3. To solve this let us rewrite the three functions.

$$2^{n/2}=(2^{1/2})^n=(\sqrt{2})^n \ \ \ (1)$$

$$3^{n/3}=(3^{1/3})^n=(\sqrt[3]{3})^n \ \ \ (2)$$

$$5^{n/5}=(5^{1/5})^n=(\sqrt[5]{5})^n \ \ \ (3)$$

Now all we have to do is to see which number inside the brackets is larger. For 1. we have $\approx1.414^n$, for 2. we have $\approx1.442^n$ and for 3. we have $\approx1.380^n$. Since 2. is larger than both 1. and 3. it is therefore the one with the greatest growth rate.

-
"[$10000^{10000/n}$] will grow at a smaller and smaller rate." Or even, not grow at all: it is a decreasing function! – Rahul Mar 9 '12 at 10:19
Also, it's pointing out that $x^{1/x}$ is maximized at $x = e \approx 2.718\ldots$, which suggests (but doesn't prove) that the value at $x = 3$ should be greater than the other options. – Rahul Mar 9 '12 at 10:25