I am very confused with this problem: arrange the following functions in ascending order of growth rates for these functions. I know based on Big O ranking, that $100$ is the fastest and $2^n$ is the slowest. I am uncertain on comparing functions especially these that have long exponents. Any help would be great! Thank you!
[Math] Arranging functions in order of growth rate
algorithmsasymptoticsfunctions
Best Answer
You have it backwards - big $O$ describes how the function behaves over large $n$. The function $f(n) = 100$ doesn't grow at all, whereas $g(n) = 2^n$ grows quite rapidly.
For the particular problem the important part is simplifying the $\log$ expressions - here are the important rules for this:
$a^{\log_a{x}} = x$
$ b \log y = \log y^b$
If you apply this you can simplify some of the log expressions.
The other thing to note is that $n$ grows faster than any power of $\log n$, and $a^n$ grows faster than any polynomial in $n$.
Example:
$$ 2^{3 \log_2 n} = 2^{\log_2 n^3} = n^3$$
where I first use the second rule I mention above and then use the first rule.