How would I go about solving the following problem?
Rank the following functions in order of their asymptotic growth.
a) $2^n$
b) $n^{1.5} - log_2{n}$
c) $n^2 - 1$
d) $n!$
e) $2^{log_2{n}}$
f) $3^n$
g) $n$log$n$
h) $\sqrt{n}$
So far, I have h<a<f<d (where h has the slowest growth). Though I am not sure where the other 4 options fit in.
Any help would be appreciated. Thanks!
Asymptotic growth of functions is often modelled with "big-O" notation: it effectively describes a tight bound for the growth of the function. For instance, $f(x)=x^2+x^1+1$ is $O(x^2)$, $f(x)=x^2+e^x$ is $O(e^x)$; you can see that the growth of the function is determined by its fastest-growing term, and that there is a ranking between different types of functions in terms of their growth rate. That ranking is, for the functions you're concerned with: $$...>O(x!) > ...>O((n+1)^x)>O(n^x)>...>O(x^{n+1})>O(x^n)>...>O(log(x))>...$$
So, by finding the big-O form of your functions, we can rank them by asymptotic growth.
a) $2^n$ is $O(2^n)$
b) $n^{1.5}−log_2(n)$ is $O(n^{1.5})$
c) $n^2−1$ is $O(n^2)$
d) $n!$ is $O(n!)$
e) $2^{log_2(n)}=n$ is $O(n)$
f) $3^n$ is $O(3^n)$
g) $n\cdot log(n)$ is $O(n\cdot log(n))$
h) $\sqrt{n}$ is $O(\sqrt{n})$, i.e., $O(n^{0.5})$
Using the ranking above, and recognising that $O(f\cdot g)\geq max\{O(f)+O(g)\}$, this gives us:
d > f > a > c > b > g > e > h