https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Big_O_notation&feed=atom&action=history Big O notation - Revision history 2024-03-29T06:02:52Z Revision history for this page on the wiki MediaWiki 1.38.4 https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Big_O_notation&diff=1276&oldid=prev Luedecke: Luedecke moved page Asymptotic notation to Big O notation 2014-10-18T16:04:44Z <p>Luedecke moved page <a href="/Asymptotic_notation" class="mw-redirect" title="Asymptotic notation">Asymptotic notation</a> to <a href="/Big_O_notation" title="Big O notation">Big O notation</a></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <tr class="diff-title" lang="en"> <td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 16:04, 18 October 2014</td> </tr><tr><td colspan="2" class="diff-notice" lang="en"><div class="mw-diff-empty">(No difference)</div> </td></tr></table> Luedecke https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Big_O_notation&diff=1275&oldid=prev Luedecke at 16:03, 18 October 2014 2014-10-18T16:03:56Z <p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 16:03, 18 October 2014</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Line 1:</td> <td colspan="2" class="diff-lineno">Line 1:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>:&lt;math&gt;\Theta(g(n)) = {f(n) : there exist positive constants <del style="font-weight: bold; text-decoration: none;">c1</del>,<del style="font-weight: bold; text-decoration: none;">c2 </del>and <del style="font-weight: bold; text-decoration: none;">n0 such that 0</del>&lt;<del style="font-weight: bold; text-decoration: none;">=''c''</del>&lt;<del style="font-weight: bold; text-decoration: none;">sub</del>&gt;<del style="font-weight: bold; text-decoration: none;">1</del>&lt;<del style="font-weight: bold; text-decoration: none;">/sub</del>&gt;<del style="font-weight: bold; text-decoration: none;">*g</del>(n) <del style="font-weight: bold; text-decoration: none;">&lt;= </del>f(n) <del style="font-weight: bold; text-decoration: none;">&lt;= c2*g</del>(n) for all &gt;<del style="font-weight: bold; text-decoration: none;">= n0 </del>}&lt;/math&gt;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>:&lt;math&gt;\Theta(g(n)) = <ins style="font-weight: bold; text-decoration: none;">\</ins>{f(n) :<ins style="font-weight: bold; text-decoration: none;">&lt;/math&gt; </ins>there exist positive constants <ins style="font-weight: bold; text-decoration: none;">&lt;math&gt;c_1&lt;/math&gt;</ins>,<ins style="font-weight: bold; text-decoration: none;">&lt;math&gt;c_2&lt;/math&gt; </ins>and &lt;<ins style="font-weight: bold; text-decoration: none;">math&gt;n_0</ins>&lt;<ins style="font-weight: bold; text-decoration: none;">/math</ins>&gt; <ins style="font-weight: bold; text-decoration: none;">such that </ins>&lt;<ins style="font-weight: bold; text-decoration: none;">math</ins>&gt;<ins style="font-weight: bold; text-decoration: none;">0\le \;c_1g</ins>(n) <ins style="font-weight: bold; text-decoration: none;">\le \; </ins>f(n) <ins style="font-weight: bold; text-decoration: none;">\le \; c_2g</ins>(n)<ins style="font-weight: bold; text-decoration: none;">&lt;/math&gt; </ins>for all <ins style="font-weight: bold; text-decoration: none;">&lt;math</ins>&gt;<ins style="font-weight: bold; text-decoration: none;">n \ge \; n_0 \</ins>}&lt;/math&gt;</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">:&lt;math>O(g(n)) = \{f(n) :&lt;/math> there exist positive constants &lt;math>c&lt;/math> and &lt;math>n_0&lt;/math> such that &lt;math>0\le \; f(n) \le \; cg(n)&lt;/math> for all &lt;math>n \ge \; n_0 \}&lt;/math></ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>:&lt;math&gt;<del style="font-weight: bold; text-decoration: none;">O</del>(g(n)) = {f(n) : there exist positive constants <del style="font-weight: bold; text-decoration: none;">c1,c2 and n0 such that 0</del>&lt;<del style="font-weight: bold; text-decoration: none;">=''</del>c<del style="font-weight: bold; text-decoration: none;">''</del>&lt;<del style="font-weight: bold; text-decoration: none;">sub</del>&gt;<del style="font-weight: bold; text-decoration: none;">1</del>&lt;/<del style="font-weight: bold; text-decoration: none;">sub</del>&gt;<del style="font-weight: bold; text-decoration: none;">*g</del>(n) <del style="font-weight: bold; text-decoration: none;">&lt;= </del>f(n) &lt;<del style="font-weight: bold; text-decoration: none;">= c2*g(n) </del>for all &gt;<del style="font-weight: bold; text-decoration: none;">= n0 </del>}&lt;/math&gt;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>:&lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\Omega</ins>(g(n)) = <ins style="font-weight: bold; text-decoration: none;">\</ins>{f(n) :<ins style="font-weight: bold; text-decoration: none;">&lt;/math&gt; </ins>there exist positive constants &lt;<ins style="font-weight: bold; text-decoration: none;">math&gt;</ins>c&lt;<ins style="font-weight: bold; text-decoration: none;">/math&gt; and &lt;math</ins>&gt;<ins style="font-weight: bold; text-decoration: none;">n_0</ins>&lt;/<ins style="font-weight: bold; text-decoration: none;">math</ins>&gt; <ins style="font-weight: bold; text-decoration: none;">such that &lt;math&gt;0 \le \; cg</ins>(n)<ins style="font-weight: bold; text-decoration: none;">\le \; </ins>f(n)&lt;<ins style="font-weight: bold; text-decoration: none;">/math&gt; </ins>for all <ins style="font-weight: bold; text-decoration: none;">&lt;math</ins>&gt;<ins style="font-weight: bold; text-decoration: none;">n \ge \; n_0 \</ins>}&lt;/math&gt;</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">:&lt;math>o(g(n)) = \{f(n) :&lt;/math> for any positive constant &lt;math>c > 0&lt;/math>, there exists ac constant &lt;math>n_0 > 0&lt;/math> such that &lt;math>0 \le \; f(n) &lt; cg(n)&lt;/math> for all &lt;math>n \ge \; n_0 \}&lt;/math></ins></div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">:&lt;math>\Omega(g(n)) = {f(n) : there exist positive constants c1,c2 and n0 such that 0&lt;=''c''&lt;sub>1&lt;/sub>*g(n) &lt;= f(n) &lt;= c2*g(n) for all >= n0 }&lt;/math></del></div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">:&lt;math>o(g(n)) = {f(n) : there exist positive constants c1,c2 and n0 such that 0&lt;=''c''&lt;sub>1&lt;/sub>*g(n) &lt;= f(n) &lt;= c2*g(n) for all >= n0 }&lt;/math></del></div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[File:anots.png]]</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>[[File:anots.png]]</div></td></tr> </table> Luedecke https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Big_O_notation&diff=46&oldid=prev Luedecke at 00:50, 10 September 2014 2014-09-10T00:50:44Z <p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 00:50, 10 September 2014</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l10">Line 10:</td> <td colspan="2" class="diff-lineno">Line 10:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>:&lt;math&gt;o(g(n)) = {f(n) : there exist positive constants c1,c2 and n0 such that 0&lt;=''c''&lt;sub&gt;1&lt;/sub&gt;*g(n) &lt;= f(n) &lt;= c2*g(n) for all &gt;= n0 }&lt;/math&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>:&lt;math&gt;o(g(n)) = {f(n) : there exist positive constants c1,c2 and n0 such that 0&lt;=''c''&lt;sub&gt;1&lt;/sub&gt;*g(n) &lt;= f(n) &lt;= c2*g(n) for all &gt;= n0 }&lt;/math&gt;</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[File:anots.<del style="font-weight: bold; text-decoration: none;">jpg</del>]]</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[File:anots.<ins style="font-weight: bold; text-decoration: none;">png</ins>]]</div></td></tr> </table> Luedecke https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Big_O_notation&diff=45&oldid=prev Luedecke at 00:50, 10 September 2014 2014-09-10T00:50:15Z <p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 00:50, 10 September 2014</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l10">Line 10:</td> <td colspan="2" class="diff-lineno">Line 10:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br/></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>:&lt;math&gt;o(g(n)) = {f(n) : there exist positive constants c1,c2 and n0 such that 0&lt;=''c''&lt;sub&gt;1&lt;/sub&gt;*g(n) &lt;= f(n) &lt;= c2*g(n) for all &gt;= n0 }&lt;/math&gt;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>:&lt;math&gt;o(g(n)) = {f(n) : there exist positive constants c1,c2 and n0 such that 0&lt;=''c''&lt;sub&gt;1&lt;/sub&gt;*g(n) &lt;= f(n) &lt;= c2*g(n) for all &gt;= n0 }&lt;/math&gt;</div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[[File:anots.jpg]]</ins></div></td></tr> </table> Luedecke https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Big_O_notation&diff=41&oldid=prev Luedecke at 00:36, 10 September 2014 2014-09-10T00:36:17Z <p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 00:36, 10 September 2014</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Line 1:</td> <td colspan="2" class="diff-lineno">Line 1:</td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&lt;math&gt;<del style="font-weight: bold; text-decoration: none;">x^</del>{<del style="font-weight: bold; text-decoration: none;">a+b</del>}&lt;/math&gt;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">:</ins>&lt;math&gt;<ins style="font-weight: bold; text-decoration: none;">\Theta(g(n)) = </ins>{<ins style="font-weight: bold; text-decoration: none;">f(n) : there exist positive constants c1,c2 and n0 such that 0&lt;=''c''&lt;sub&gt;1&lt;/sub&gt;*g(n) &lt;= f(n) &lt;= c2*g(n) for all &gt;= n0 }&lt;/math&gt;</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">:&lt;math&gt;O(g(n)) = {f(n) : there exist positive constants c1,c2 and n0 such that 0&lt;=''c''&lt;sub&gt;1&lt;/sub&gt;*g(n) &lt;= f(n) &lt;= c2*g(n) for all &gt;= n0 }&lt;/math&gt;</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">:&lt;math&gt;\Omega(g(n)) = {f(n) : there exist positive constants c1,c2 and n0 such that 0&lt;=''c''&lt;sub&gt;1&lt;/sub&gt;*g(n) &lt;= f(n) &lt;= c2*g(n) for all &gt;= n0 }&lt;/math&gt;</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">:&lt;math&gt;o(g(n)) = {f(n) : there exist positive constants c1,c2 and n0 such that 0&lt;=''c''&lt;sub&gt;1&lt;/sub&gt;*g(n) &lt;= f(n) &lt;= c2*g(n) for all &gt;= n0 </ins>}&lt;/math&gt;</div></td></tr> </table> Luedecke https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Big_O_notation&diff=40&oldid=prev Luedecke: Created page with "<math>x^{a+b}</math>" 2014-09-09T23:53:29Z <p>Created page with &quot;&lt;math&gt;x^{a+b}&lt;/math&gt;&quot;</p> <p><b>New page</b></p><div>&lt;math&gt;x^{a+b}&lt;/math&gt;</div> Luedecke