Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I fixed your formatting; is everything as you intended? –  chris May 19 '12 at 3: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 3:53
    
It may be easier to work with the logarithms of all of these functions. –  André Nicolas May 19 '12 at 3: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 4:11
1  
@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 4:19

1 Answer 1

up vote 6 down vote accepted

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

share|improve this answer
    
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 4:42
    
@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 4:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.