Difference between revisions of "TADM2E 2.7"
From Algorithm Wiki
(Recovering wiki) 
(No difference)

Revision as of 18:14, 11 September 2014
True or False?
Is <math>2^{n+1} = O (2^n)</math>?
True
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: <math>2^{n+1} = O (2^n)</math>.
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 <math>2^{2n} = O(2^n)</math>?
False
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 <math>2^{2n}</math> is strictly larger than <math>2^n</math>.
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 AlgoanalysisTADM2E ...