9

How can I go about comparing the growth rate of the following functions?

$$\sqrt n,\quad 10^n,\quad n^{1.5},\quad 2^{\sqrt{\log n}},\quad n^{5/3}.$$

I am looking for a more generic answer on how do we go about comparing growth rate of functions and a small example demonstrating it on this set of functions would be really helpful.Any links or references explaining the topic would also be very helpful.

Bunny Rabbit
  • 467
  • I fixed your formatting; is everything as you intended? – chris May 19 '12 at 03:52
  • 2
    Compute limits of quotients. For example, $\lim\limits_{n\rightarrow\infty}{\sqrt n\over 10^n}=0$, by L'Hopital's rule e.g. So $\sqrt n$ grows more slowly than $10^n$. To save time, you might play around with the expressions first (evaluate them for various $n$) to determine their order in terms of their growth rates; then prove your ordering is correct. – David Mitra May 19 '12 at 03:53
  • It may be easier to work with the logarithms of all of these functions. – André Nicolas May 19 '12 at 03:56
  • @chris Yes thanks :) – Bunny Rabbit May 19 '12 at 03:56
  • 1
    Generically? exponentials beat positive powers, larger positive powers beat smaller positive powers, positive powers beat logarithms. Is that the sort of thing you are talking about? – Arturo Magidin May 19 '12 at 04:11
  • @ArturoMagidin Yes , i am aware of this sort of things but I am not sure why and when we need to take limits of the functions and to which values these limits should tend and when do we need to take derivatives. – Bunny Rabbit May 19 '12 at 04:14
  • 2
    @Bunny: "When we need to take the limits". One takes the limits in order to establish those facts. If $f$ "beats" $g$ in the sense above, then the limit of $f/g$ will be $\infty$ and the limit of $g/f$ will be $0$. When the limit is a positive constant, the growth rates are "comparable"; e.g., $10n^3$ and $5n^3$ have "comparable growth". – Arturo Magidin May 19 '12 at 04:19

1 Answers1

13

Generically: exponentials beat positive powers; larger (positive) powers beat smaller (positive) powers; (positive) powers beat logarithms.

Among exponentials, you can always convert them all to the same base and compare exponents; larger exponents beat smaller ones. Same for logarithms.

So you know that $10^n$ will grow the fastest; with $2^{\log n}$ you have to be careful, because it looks exponential, but an exponential raised to a logarithm is actually not exponential: $$2^{\log n} = e^{(\log n)(\log 2)} = (e^{\log n})^{\log 2} = n^{\log 2},$$ so this is actually just a power.

Among the powers, you have $n^{1/2}$, $n^{\log 2}$, $n^{1.5}$, and $n^{5/3}$. Comparing the exponents, we have $$\frac{1}{2}\lt \log 2 \lt 1.5 \lt \frac{5}{3}$$ so that's the order of growth of the functions. So we have (with $\succ$ meaning "grows faster than") $$10^n \succ n^{5/3} \succ n^{1/5} \succ 2^{\log n}=n^{\log 2} \succ \sqrt{n}.$$

Arturo Magidin
  • 398,050
  • 1
    Can you provide a little explanation on how did you convert $2^{\log n} to $e^{(\log n)(\log 2)} – Bunny Rabbit May 19 '12 at 04:42
  • 3
    @BunnyRabbit: Well, by definition, $a^b = e^{b\ln(a)}$. But if you don't remember that, take the log and then the exponential: $$a^b = e^{\ln(a^b)} = e^{b\ln a}.$$In particular,$$2^{\log n} = e^{\log(2^{\log n})} = e^{(\log n)(\log 2)}$$using the property of logarithms that says that $\log(r^s) = s\log r$. I am assuming that $\log$ means logarithm base $e$: otherwise, if it is logarithm base 10, then the conversion should be $$2^{\log n} = 10^{\log(2^{\log n})} = 10^{(\log n)(\log 2)} = (10^{\log n})^{\log 2} = n^{\log 2}.$$ – Arturo Magidin May 19 '12 at 04:45