Difference between revisions of "TADM2E 2.7"

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 Algo-analysis-TADM2E ...