# time complexity – 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$$ Posted on Categories Articles