7
$\begingroup$

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.

  • 0
    I fixed your formatting; is everything as you intended?2012-05-19
  • 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.2012-05-19
  • 0
    It may be easier to work with the logarithms of all of these functions.2012-05-19
  • 0
    @chris Yes thanks :)2012-05-19
  • 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?2012-05-19
  • 0
    @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.2012-05-19
  • 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".2012-05-19

1 Answers 1

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}.$$

  • 1
    Can you provide a little explanation on how did you convert $2^{\log n} to $e^{(\log n)(\log 2)}2012-05-19
  • 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}.$$2012-05-19