Difference between revisions of "TADM2E 2.7"
From Algorithm Wiki
(Recovering wiki) |
(Recovering wiki) |
||
| Line 1: | Line 1: | ||
True or False? | True or False? | ||
| − | ==Is | + | ==Is <math>2^{n+1} = O (2^n)</math>?== |
True | True | ||
| Line 6: | Line 6: | ||
''Proof'': | ''Proof'': | ||
| − | + | <math>2^{n+1}=2 \times 2^n</math>, | |
| − | + | <math>2^{n+1} \le 2 \times 2^n</math>, | |
| − | + | <math>2^{n+1} \le C \times 2^n</math> (where <math>C=2</math>), | |
Thus: | Thus: | ||
| − | + | <math>2^{n+1} = O (2^n)</math>. | |
| − | In fact, | + | In fact, <math>2^n = O(2^{n+1})</math> as well, because <math>2^n \le 2^{n+1}</math>, thus <math>2^n \le C \times 2^{n+1}</math> (where <math>C=1</math>). |
| − | ==Is | + | ==Is <math>2^{2n} = O(2^n)</math>?== |
False | False | ||
''Proof'': | ''Proof'': | ||
| − | + | <math>\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</math> | |
| − | This means that | + | This means that <math>2^{2n}</math> is strictly larger than <math>2^n</math>. |
| − | Thus | + | Thus <math>2^n = o(2^{2n})</math>, which means that <math>2^n = O(2^{2n})</math>, though <math>2^{2n} \ne O(2^n)</math>. |
Return to [[Algo-analysis-TADM2E]] ... | Return to [[Algo-analysis-TADM2E]] ... | ||
Latest revision as of 18:23, 11 September 2014
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 ...
