# 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$$

• $\frac{f_3}{f_2}(n)=\frac{n^{100}}{(2^{1/2})^n}$. If you consider the corresponding function over the reals and do L'Hospital you would have to consider the quotient $\frac{100x^{99}}{(2^{1/2})^x\log(2^{1/2})}$. The degree of the polynomial in the numerator decreased. You can apply L'Hospital $99$ more times to get to $\frac{100!}{(2^{1/2})^x(\log(2^{1/2}))^{100}}$. This tends to $0$ as $x\to+\infty$. So, $f_3\in O(f_2)$.
– plop
Sep 30, 2020 at 12:41
• To compare $f_1$ and $f_2$ maybe compare $g_1(n)=\log(f_1(n))=n^{1/2}\log(n)$ and $g_2(n)=\log(f_2(n))=n\log(2)$. If, for example, you do $\frac{g_1}{g_2}(n)=\frac{\log(n)}{n^{1/2}\log(2)}$. Using L'Hospital as before, you get to consider the limit of $\frac{1/x}{\frac{1}{2}\log(2)x^{-1/2}}=2(\log(2))^{-1}x^{-1/2}\to0$ as $x\to+\infty$. Therefore, there is some $n_0$ such that for all $n\geq n_0$ we have $g_1(n)\leq g_2(n)$. Applying $e^x$, which is increasing, on both sides we get that $f_1(n)\leq f_2(n)$, for all $n\geq n_0$. So, $f_1\in O(f_2)$.
– plop
Sep 30, 2020 at 12:56

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.