How do I show that one function isn't growing slower or equal than the other I had a lecture on BigO notation, and I received a problem set to solve, but unfortunately we always get harder examples to solve that those presented(those which are presented are always some basic cases) during the lecture.
Here is the actual question: check if:   $2^n = O(n^2) $
For sure it's false because $2^n$ grows much faster than $n^2$, but I have no idea how to show that.
 A: Show that
$$\lim_{n\rightarrow\infty} Cn^2/2^n=0$$
for any $C$. Can be done with L'Hopital's rule in a straightforward fashion.
A: Hints:
First, recall the gist and definition of big $O$ notation given by your syllabus. The gist is that we write $f(n)=O(g(n))$ if, as $n$ increases, $g$ grows faster than, or as fast as, $f$. It should be fairly clear which of $2^n$ and $n^2$ grows faster. The typical full definition is that for two real-valued functions of real variables $f$ and $g$, if all sufficiently large arguments $n>n_0$ have $|f(n)|$ equal to or bounded above by $Mg(n)$ for some positive real constant $M$, then we write that $f(n)=O(g(n))$.
So, in this case, we are asking whether it is possible to construct the bound $2^n\le Mn^2$ for all $n>n_0$ and some $M>0$.
Then, manipulate the inequality $2^n\le Mn^2$ with the aim of deriving a contradiction. One way to do this might be as $\displaystyle \frac{Mn^{2}}{2^{n}}-1\ge0$ and then expanding $2^n$ in order to compare it with polynomials.
