TADM2E 2.7

True or False?

Is $2^{n+1} = O (2^n)$ ?

True

Proof:

$2^{n+1}=2 \times 2^n$ ,

$2^{n+1} \le 2 \times 2^n$ ,

$2^{n+1} \le C \times 2^n$ (where $$ C=2 $$ ),

Thus: $2^{n+1} = O (2^n)$ .

In fact, $2^n = O(2^{n+1})$ as well, because $2^n \le 2^{n+1}$ , thus $2^n \le C \times 2^{n+1}$ (where $$ C=1 $$ ).

False

Proof:

$\lim_{n \to \infty} \frac{2^n}{2^{2n}} = \lim_{n \to \infty} \frac{2^n}{4^n} = \lim_{n \to \infty} (\frac{2}{4})^n = 0$

This means that $2^{2n}$ is strictly larger than $$ 2^n $$ .

Thus $2^n = o(2^{2n})$ , which means that $2^n = O(2^{2n})$ , though $2^{2n} \ne O(2^n)$ .