# TADM2E 2.7

From Algorithm Wiki

Revision as of 18:23, 11 September 2014 by Algowikiadmin (Talk | contribs)

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