Is $2^{2n} = O(2^n)$?
My solution is:
$2^n 2^n \leq C_{1}2^n$
$2^n \leq C_{1}$,
TRUE.
Is this correct?
$\endgroup$ 82 Answers
$\begingroup$If $2^{2n}=O(2^n)$, then there is a constant $C$ and an integer $M$ such that for all $n\ge M$, the inequality $2^{2n}\le C 2^n$ holds.
This would imply that $2^n\cdot 2^n\le C 2^n$ for all $n\ge M$, which in turn implies $$\tag{1} 2^n\le C \quad {\bf for\ all } \quad n\ge M. $$ Can such $C$ and $M$ exist? Note the right hand side of $(1)$ is fixed, and the left hand side...
$\endgroup$ 1 $\begingroup$$x^n=o(y^n)$ iff $x<y$, as $(\frac{x}{y})^n\rightarrow 0$. Here 4 and 2, so no.
$\endgroup$
