Algowikiadmin: Recovering wiki

2014-09-11T18:23:56Z

Recovering wiki

Algowikiadmin: Recovering wiki

2014-09-11T18:14:12Z

Recovering wiki

New page

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

@@ Line 1: / Line 1: @@
 True or False?
-==Is &lt;math&gt;2^{n+1} = O (2^n)&lt;/math&gt;?==
+==Is <math>2^{n+1} = O (2^n)</math>?==
 True
@@ Line 6: / Line 6: @@
 ''Proof'':
-&lt;math&gt;2^{n+1}=2 \times 2^n&lt;/math&gt;,
+<math>2^{n+1}=2 \times 2^n</math>,
-&lt;math&gt;2^{n+1} \le 2 \times 2^n&lt;/math&gt;,
+<math>2^{n+1} \le 2 \times 2^n</math>,
-&lt;math&gt;2^{n+1} \le C \times 2^n&lt;/math&gt; (where &lt;math&gt;C=2&lt;/math&gt;),
+<math>2^{n+1} \le C \times 2^n</math> (where <math>C=2</math>),
 Thus:
-&lt;math&gt;2^{n+1} = O (2^n)&lt;/math&gt;.
+<math>2^{n+1} = O (2^n)</math>.
-In fact, &lt;math&gt;2^n = O(2^{n+1})&lt;/math&gt; as well, because &lt;math&gt;2^n \le 2^{n+1}&lt;/math&gt;, thus &lt;math&gt;2^n \le C \times 2^{n+1}&lt;/math&gt; (where &lt;math&gt;C=1&lt;/math&gt;).
+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 &lt;math&gt;2^{2n} = O(2^n)&lt;/math&gt;?==
+==Is <math>2^{2n} = O(2^n)</math>?==
 False
 ''Proof'':
-&lt;math&gt;\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&lt;/math&gt;
+<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 &lt;math&gt;2^{2n}&lt;/math&gt; is strictly larger than &lt;math&gt;2^n&lt;/math&gt;.
+This means that <math>2^{2n}</math> is strictly larger than <math>2^n</math>.
-Thus &lt;math&gt;2^n = o(2^{2n})&lt;/math&gt;, which means that &lt;math&gt;2^n = O(2^{2n})&lt;/math&gt;, though &lt;math&gt;2^{2n} \ne O(2^n)&lt;/math&gt;.
+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]] ...

TADM2E 2.7 - Revision history

Algowikiadmin: Recovering wiki

Algowikiadmin: Recovering wiki