Figuring out which functions are Big-O of other functions (of a of 9 different functions). Where do I start? Problem
I need to arrange the following functions in order, so that each function is big-oh of the next function.
Functions

Attempt @ Solution


*

*Understanding: I don't understand what to do here.  My best guess is to determine what each function is Big-Oh of, and then rank the functions in order of magnitude of Big-Oh.  Is that a way to start?

 A: The problem is essentially to rank the nine functions in order of increasing growth rates. You know, for instance, that $2^n$ grows faster than $n^2$, and hence that $n^2$ is $O(2^n)$; thus, $n^2$ will come somewhere before $2^n$ in your ranking.
The first five are already fairly basic functions: you should definitely know the proper order for $n!$, $2^n$, $n^2$, $\sqrt n$, and you should probably know where $\log_2n$ fits into that list. The other four will require some work; in each case it would be helpful to find a simple function $g(n)$ such that the given function is $\Theta\big(g(n)\big)$, i.e., both $O\big(g(n)\big)$ and $\Omega\big(g(n)\big)$. 
I’ll get you started on one of them and add some hints for the rest. From the formula for the sum of a geometric series you know that $$\sum_{i=0}^n2^i=\frac{2^{n+1}-2^0}{2-1}=2^{n+1}-1\;.$$ This suggests that you should try to show that $\sum_{i=0}^n2^i$ is $\Theta(2^{n+1})$, since for large $n$ that $-1$ is going to be insignificant.
You may have to dig it out, but there’s a known formula for the sum of the first $n$ perfect squares; you can use that to work out the growth rate of $\sum_{i=0}^ni^2$. Use the properties of logarithms to simplify $\sum_{i=1}^n\log_2i$; it’s the log base $2$ of what function of $n$? As for the last one, what limit does it approach as $n\to\infty$?
A: For a starter, the last function is the slowest, because you can take (numerator is $a(n)$, denominator $d(n)$:
$$
\frac{a(n)}{d(n)}\leq \frac{(n+3)^3}{(n-3)^3} \leq \frac{3n^3}{\frac{n^3}{3}}=9=O(1)
$$
The rest of your functions are $\omega(1)$, i.e. the tend to infinity as $n \to \infty$
