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 :
$2^{n/2}$
$3^{n/3}$
$5^{n/5}$
$1000^{1000/n}$
$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?
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.