0
$\begingroup$

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)$.

$\endgroup$
4
  • 2
    $\begingroup$ Because taking the logarithm gives you $1 \leq n \leq \log_2(c) + n/2$ which is not true for large $n$. $\endgroup$ Feb 14 at 15:24
  • $\begingroup$ Ah yes thanks. I don't know why i decided not to include c and 0 when i took $lg$. $\endgroup$
    – sn3jd3r
    Feb 14 at 15:25
  • $\begingroup$ If $c < 1$ then $\log_2 c < 0$ $\endgroup$ Feb 14 at 15:25
  • 6
    $\begingroup$ 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. $\endgroup$
    – Bernard
    Feb 14 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.