Proving that $f(x)=2^x$ is $O(x^2)$

Question

Can someone help me with this problem? I don't really know what to do if the x is in exponential form.

Answer 1

To see that this is way false, we just observe:

$$2^x\le Mx^2\iff x\log 2\le \log M+2\log x$$

$$\iff x\le \log_2(M)+2\log_2(x)$$

But it is clear from L'Hôpital's rule (among other things) that this is false, since

$$\lim_{x\to\infty} {M\over x\log 2}+{2\log x\over x\log 2}=\lim_{x\to\infty} {2/x\over \log 2}=0$$

---

(in fact this would imply)

$$x=O(\log x)$$

Answer 2

Suppose that there is $M\in\mathbb{R}$ such that $2^x\leqslant M\cdot x^2,\;\forall\; x\geqslant x_0$.

That is suppose that $2^x\in O(x^2)$.

Then, $\dfrac{e^{x\log2}}{x^2}\leqslant M,\;\forall\; x\geqslant x_0$. Let $x\rightarrow \infty$, then $\lim_{x\to\infty}\dfrac{e^{x\log2}}{x^2}=\infty\leqslant M$. Absurd.

Hence, $2^x\not\in O(x^2)$.

Answer 3

A direct proof (that is, not by contradiction):

For every $z\geqslant0$, one has $2^z\gt z$. Using this for $z=x/3$ and raising both sides to their cubes yields $2^x\gt x^3/27$ for every $x\geqslant0$. In particular, $2^x/x^2\geqslant x/27$ hence $2^x/x^2\to+\infty$ when $x\to+\infty$.

To prove that $2^z\gt z$ for $z\gt1$, one can write $2^z=(1+1)^z\gt1+z\cdot1\gt z$.