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.
$\endgroup$ 71 Answer
$\begingroup$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}.$$
$\endgroup$ 2
