TADM2E 2.7

From Algorithm Wiki
Revision as of 18:23, 11 September 2014 by Algowikiadmin (talk | contribs) (Recovering wiki)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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 ...