Comparing the big-$O$ of these four functions Sometimes you can substitute values for $n_0$ and $c$ in the big-$O$ equation and compare two functions. Or take limits and compare two functions.
But for the following functions, for example, taking the limit in infinity for
$f_3$ over $f_2$ requires using l'Hôpital's rule which doesn't simplify anything. $f_3$ is technically the product of a polynomial and an exponential function. And I don't know how to go with comparing functions like that with others.
Firstly, I know that $f_4$ is the most efficient because it is $O(n^2)$. ($f_4(n) = n + \frac{n(n + 1)}{2}$) and the rest are exponential.
But for the rest, I really don't know what to besides using my intuition which could be really far from the correct answer anyway. Please help me compare these rigorously.
$f_1(n) = n^{\sqrt{n}}$
$f_2(n) = 2^n$
$f_3(n) = n^{100}2^{\frac{n}{2}}$
$f_4(n) = \Sigma_{i=1}^{n}i + 1$
One useful technique for comparing functions asymptotically is to take their logs since doing that turns exponentials into polynomials. So, if you are comfortable with comparing polynomials, then taking logs is always something you should be thinking about.
There is one thing that you have to be careful of when you do that, however. After taking logs, you can not throw away constant factors anymore.
If you take the logs of your functions, you get $\log(f_1(n))=\sqrt{n}\log(n)$, $\log(f_2(n))=n\log(2)$ and $\log(f_3(n))= 100\log(n)+\frac{n}{2}\log(2)$. So, $f_2$ is asymptotically larger than $f_3$ which, in turn is asymptotically larger than $f_1$. You already know where $f_4$ goes.