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.

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

  • 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