4
$\begingroup$

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?

  • 0
    Hint: Think of the growth rate as the derivative of the function.2012-03-09

1 Answers 1

9

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.

  • 4
    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.2012-03-09