Comparing Big O Complexity
If $$\limsup_{n \rightarrow \infty} \frac{g(n)}{f(n)} &lt; \infty,$$ then we have that $g(n)$ is $O(f(n))$. 

That is actually (almost) the definition of the big-O notation (modulo the $| \cdot |$ function that I left out for readability). You would prove that using your math knowledge. Note that if you can show that $$\lim_{n \rightarrow \infty} \frac{g(n)}{f(n)} &lt; \infty,$$ for strictly increasing positive functions $g$ and $f$, this implies the satisfaction of the first equation. Analyzing the latter function should be part of most computer science curricula.