TADM2E 2.7

Jump to: navigation, search

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

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

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

Return to Algo-analysis-TADM2E ...