Why is $2^n \neq O\left (2^{\frac{n}{2}} \right)$?

According to the solutions to problem 3-2 in CLRS $$2^n \neq O\left (2^{\frac{n}{2}} \right)$$. Why is the following proof wrong?

We wish to show that: $$0 \leq 2^n \leq c 2^{\frac{n}{2}}$$ for all $$n\geq n_0$$ and some $$c > 0$$. \begin{align*} 0 \leq 2^n \leq c 2^{\frac{n}{2}} \implies 0 \leq n \leq \frac{cn}{2} \end{align*} This is true for $$n_0 = 0$$ and $$c \geq 2$$ so $$2^n = O\left (2^{\frac{n}{2}} \right)$$.

• Because taking the logarithm gives you $1 \leq n \leq \log_2(c) + n/2$ which is not true for large $n$. Feb 14 at 15:24
• Ah yes thanks. I don't know why i decided not to include c and 0 when i took $lg$. Feb 14 at 15:25
• If $c < 1$ then $\log_2 c < 0$ Feb 14 at 15:25
• Anyway, $2^n\ne O\bigl(2^{n/2}\bigr)$ simply because the ratio $\dfrac{2^n}{2^{n/2}}=2^{n/2}\:$ is not bounded. Feb 14 at 15:28