Asymptotic complexity of algorithms - Revision history

https://wiki.algo.informatik.tu-darmstadt.de/index.php?action=history&feed=atom&title=Asymptotic_complexity_of_algorithms Asymptotic complexity of algorithms - Revision history 2026-04-04T18:05:58Z Revision history for this page on the wiki MediaWiki 1.38.4 https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Asymptotic_complexity_of_algorithms&diff=3811&oldid=prev Weihe: /* Bounds on the asymtptotic complexity */ 2016-04-25T05:54:50Z

<p><span dir="auto"><span class="autocomment">Bounds on the asymtptotic complexity</span></span></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 05:54, 25 April 2016</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l32">Line 32:</td> <td colspan="2" class="diff-lineno">Line 32:</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>where "<math>\oplus</math>" is one of "<math>\mathcal{O}</math>", "<math>o</math>", "<math>\Omega</math>", and "<math>\Theta</math>".</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>where "<math>\oplus</math>" is one of "<math>\mathcal{O}</math>", "<math>o</math>", "<math>\Omega</math>", and "<math>\Theta</math>".</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;">'''Remark:'''</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><ins style="font-weight: bold; text-decoration: none;">== Asymptotic complexity analysis of an algorithm ==</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 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>An asymptotic complexity analysis of an algorithm combines two aspects: (1) which case (worst, best, average) is to be analyzed and (2) which type of [[Asymptotic comparison of functions|function class]] (<math>\mathcal{O}</math>, <math>\Omega</math>, <math>\Theta</math>, <math>o</math>) is to be determined. Note that the case and the function class are two separate concepts, which are easily confused.</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>An asymptotic complexity analysis of an algorithm combines two aspects: (1) which case (worst, best, average) is to be analyzed and (2) which type of [[Asymptotic comparison of functions|function class]] (<math>\mathcal{O}</math>, <math>\Omega</math>, <math>\Theta</math>, <math>o</math>) is to be determined. Note that the case and the function class are two separate concepts, which are easily confused.</div></td></tr> </table>

Weihe https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Asymptotic_complexity_of_algorithms&diff=3810&oldid=prev Weihe: /* Bounds on the asymtptotic complexity */ 2016-04-24T19:43:45Z

<p><span dir="auto"><span class="autocomment">Bounds on the asymtptotic complexity</span></span></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 19:43, 24 April 2016</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l31">Line 31:</td> <td colspan="2" class="diff-lineno">Line 31:</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># in the average case with respect to <math>P</math>, if <math>f_P\in\oplus(g)</math>,</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># in the average case with respect to <math>P</math>, if <math>f_P\in\oplus(g)</math>,</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;"><div>where "<math>\oplus</math>" is one of "<math>\mathcal{O}</math>", "<math>o</math>", "<math>\Omega</math>", and "<math>\Theta</math>".</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>where "<math>\oplus</math>" is one of "<math>\mathcal{O}</math>", "<math>o</math>", "<math>\Omega</math>", and "<math>\Theta</math>".</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></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;"><div>'''Remark:'''</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>'''Remark:'''</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;"><div>An asymptotic complexity analysis of an algorithm combines two aspects: (1) which case (worst, best, average) is to be analyzed and (2) which type of [[Asymptotic comparison of functions|function class]] (<math>\mathcal{O}</math>, <math>\Omega</math>, <math>\Theta</math>, <math>o</math>) is to be determined. Note that the case and the function class are two separate concepts, which are easily confused.</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>An asymptotic complexity analysis of an algorithm combines two aspects: (1) which case (worst, best, average) is to be analyzed and (2) which type of [[Asymptotic comparison of functions|function class]] (<math>\mathcal{O}</math>, <math>\Omega</math>, <math>\Theta</math>, <math>o</math>) is to be determined. Note that the case and the function class are two separate concepts, which are easily confused.</div></td></tr> </table>

Weihe https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Asymptotic_complexity_of_algorithms&diff=3809&oldid=prev Weihe at 19:43, 24 April 2016 2016-04-24T19:43:32Z

<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 19:43, 24 April 2016</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l21">Line 21:</td> <td colspan="2" class="diff-lineno">Line 21:</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>## In the '''best case''': by the function <math>f_\min:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f_{\min}(n_1,\ldots,n_k)</math> is the ''minimum'' number of operations executed by the algorithm for any instance in <math>\mathcal{I}(n_1,\ldots,n_k)</math>.</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>## In the '''best case''': by the function <math>f_\min:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f_{\min}(n_1,\ldots,n_k)</math> is the ''minimum'' number of operations executed by the algorithm for any instance in <math>\mathcal{I}(n_1,\ldots,n_k)</math>.</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;"><div>## In the '''average case''': For this case, a [http://en.wikipedia.org/wiki/Probability_distribution probability distribution] <math>P_{n_1,\ldots,n_k}</math> over each set <math>\mathcal{I}(n_1,\ldots,n_k)</math> is required. For short, let <math>P:=(P_{n_1,\ldots,n_k})_{n_1,\ldots,n_k\in\mathbb{N}}</math>. Then the asymptotic average complexity is the function <math>f_P:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f_P(n_1,\ldots,n_k)</math> is the ''expected'' number of operations executed by the algorithm, taken over all instances in <math>\mathcal{I}(n_1,\ldots,n_k)</math>, with respect to the distribution <math>P_{n_1,\ldots,n_k}</math>.</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>## In the '''average case''': For this case, a [http://en.wikipedia.org/wiki/Probability_distribution probability distribution] <math>P_{n_1,\ldots,n_k}</math> over each set <math>\mathcal{I}(n_1,\ldots,n_k)</math> is required. For short, let <math>P:=(P_{n_1,\ldots,n_k})_{n_1,\ldots,n_k\in\mathbb{N}}</math>. Then the asymptotic average complexity is the function <math>f_P:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f_P(n_1,\ldots,n_k)</math> is the ''expected'' number of operations executed by the algorithm, taken over all instances in <math>\mathcal{I}(n_1,\ldots,n_k)</math>, with respect to the distribution <math>P_{n_1,\ldots,n_k}</math>.</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><del style="font-weight: bold; text-decoration: none;">'''Remark:'''</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;">An asymptotic complexity analysis of an algorithm combines two aspects: (1) which case (worst, best, average) is to be analyzed and (2) which type of [[Asymptotic comparison of functions|function class]] (<math>\mathcal{O}</math>, <math>\Omega</math>, <math>\Theta</math>, <math>o</math>) is to be determined. Note that the case and the function class are two separate concepts, which are easily confused.</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;"><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>== Bounds on the asymtptotic complexity ==</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>== Bounds on the asymtptotic complexity ==</div></td></tr> <tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l33">Line 33:</td> <td colspan="2" class="diff-lineno">Line 31:</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># in the average case with respect to <math>P</math>, if <math>f_P\in\oplus(g)</math>,</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># in the average case with respect to <math>P</math>, if <math>f_P\in\oplus(g)</math>,</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;"><div>where "<math>\oplus</math>" is one of "<math>\mathcal{O}</math>", "<math>o</math>", "<math>\Omega</math>", and "<math>\Theta</math>".</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>where "<math>\oplus</math>" is one of "<math>\mathcal{O}</math>", "<math>o</math>", "<math>\Omega</math>", and "<math>\Theta</math>".</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;">'''Remark:'''</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><ins style="font-weight: bold; text-decoration: none;">An asymptotic complexity analysis of an algorithm combines two aspects: (1) which case (worst, best, average) is to be analyzed and (2) which type of [[Asymptotic comparison of functions|function class]] (<math>\mathcal{O}</math>, <math>\Omega</math>, <math>\Theta</math>, <math>o</math>) is to be determined. Note that the case and the function class are two separate concepts, which are easily confused.</ins></div></td></tr> </table>

Weihe https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Asymptotic_complexity_of_algorithms&diff=3808&oldid=prev Weihe: /* Asymptotic complexity of an algorithm */ 2016-04-24T19:41:45Z

<p><span dir="auto"><span class="autocomment">Asymptotic complexity of an algorithm</span></span></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 19:41, 24 April 2016</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l22">Line 22:</td> <td colspan="2" class="diff-lineno">Line 22:</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>## In the '''average case''': For this case, a [http://en.wikipedia.org/wiki/Probability_distribution probability distribution] <math>P_{n_1,\ldots,n_k}</math> over each set <math>\mathcal{I}(n_1,\ldots,n_k)</math> is required. For short, let <math>P:=(P_{n_1,\ldots,n_k})_{n_1,\ldots,n_k\in\mathbb{N}}</math>. Then the asymptotic average complexity is the function <math>f_P:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f_P(n_1,\ldots,n_k)</math> is the ''expected'' number of operations executed by the algorithm, taken over all instances in <math>\mathcal{I}(n_1,\ldots,n_k)</math>, with respect to the distribution <math>P_{n_1,\ldots,n_k}</math>.</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>## In the '''average case''': For this case, a [http://en.wikipedia.org/wiki/Probability_distribution probability distribution] <math>P_{n_1,\ldots,n_k}</math> over each set <math>\mathcal{I}(n_1,\ldots,n_k)</math> is required. For short, let <math>P:=(P_{n_1,\ldots,n_k})_{n_1,\ldots,n_k\in\mathbb{N}}</math>. Then the asymptotic average complexity is the function <math>f_P:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f_P(n_1,\ldots,n_k)</math> is the ''expected'' number of operations executed by the algorithm, taken over all instances in <math>\mathcal{I}(n_1,\ldots,n_k)</math>, with respect to the distribution <math>P_{n_1,\ldots,n_k}</math>.</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;"><div>'''Remark:'''</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>'''Remark:'''</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>An asymptotic complexity analysis of an algorithm combines two aspects: which case (worst, best, average) and which [[Asymptotic comparison of functions|function class]] (<math>\mathcal{O}</math>, <math>\Omega</math>, <math>\Theta</math>, <math>o</math>. Note that the case and the function class are two separate concepts, which are easily confused.</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>An asymptotic complexity analysis of an algorithm combines two aspects: <ins style="font-weight: bold; text-decoration: none;">(1) </ins>which case (worst, best, average) <ins style="font-weight: bold; text-decoration: none;">is to be analyzed </ins>and <ins style="font-weight: bold; text-decoration: none;">(2) </ins>which <ins style="font-weight: bold; text-decoration: none;">type of </ins>[[Asymptotic comparison of functions|function class]] (<math>\mathcal{O}</math>, <math>\Omega</math>, <math>\Theta</math>, <math>o</math><ins style="font-weight: bold; text-decoration: none;">) is to be determined</ins>. Note that the case and the function class are two separate concepts, which are easily confused.</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"></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>== Bounds on the asymtptotic complexity ==</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>== Bounds on the asymtptotic complexity ==</div></td></tr> </table>

Weihe https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Asymptotic_complexity_of_algorithms&diff=3807&oldid=prev Weihe: /* Asymptotic complexity of an algorithm */ 2016-04-24T19:40:43Z

<p><span dir="auto"><span class="autocomment">Asymptotic complexity of an algorithm</span></span></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 19:40, 24 April 2016</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l22">Line 22:</td> <td colspan="2" class="diff-lineno">Line 22:</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>## In the '''average case''': For this case, a [http://en.wikipedia.org/wiki/Probability_distribution probability distribution] <math>P_{n_1,\ldots,n_k}</math> over each set <math>\mathcal{I}(n_1,\ldots,n_k)</math> is required. For short, let <math>P:=(P_{n_1,\ldots,n_k})_{n_1,\ldots,n_k\in\mathbb{N}}</math>. Then the asymptotic average complexity is the function <math>f_P:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f_P(n_1,\ldots,n_k)</math> is the ''expected'' number of operations executed by the algorithm, taken over all instances in <math>\mathcal{I}(n_1,\ldots,n_k)</math>, with respect to the distribution <math>P_{n_1,\ldots,n_k}</math>.</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>## In the '''average case''': For this case, a [http://en.wikipedia.org/wiki/Probability_distribution probability distribution] <math>P_{n_1,\ldots,n_k}</math> over each set <math>\mathcal{I}(n_1,\ldots,n_k)</math> is required. For short, let <math>P:=(P_{n_1,\ldots,n_k})_{n_1,\ldots,n_k\in\mathbb{N}}</math>. Then the asymptotic average complexity is the function <math>f_P:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f_P(n_1,\ldots,n_k)</math> is the ''expected'' number of operations executed by the algorithm, taken over all instances in <math>\mathcal{I}(n_1,\ldots,n_k)</math>, with respect to the distribution <math>P_{n_1,\ldots,n_k}</math>.</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;"><div>'''Remark:'''</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>'''Remark:'''</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>An asymptotic complexity analysis of an algorithm combines two aspects: which case (worst, best, average) and which [[Asymptotic comparison of functions|function class]] (<math>\mathcal{O}</math>, <math>\Omega</math>, <math>\Theta<math>, <math>o</math>. Note that the case and the function class are two separate concepts, which are <del style="font-weight: bold; text-decoration: none;">frequently </del>confused.</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>An asymptotic complexity analysis of an algorithm combines two aspects: which case (worst, best, average) and which [[Asymptotic comparison of functions|function class]] (<math>\mathcal{O}</math>, <math>\Omega</math>, <math>\Theta<<ins style="font-weight: bold; text-decoration: none;">/</ins>math>, <math>o</math>. Note that the case and the function class are two separate concepts, which are <ins style="font-weight: bold; text-decoration: none;">easily </ins>confused.</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"></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>== Bounds on the asymtptotic complexity ==</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>== Bounds on the asymtptotic complexity ==</div></td></tr> </table>

Weihe https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Asymptotic_complexity_of_algorithms&diff=3806&oldid=prev Weihe: /* Asymptotic complexity of an algorithm */ 2016-04-24T19:40:16Z

<p><span dir="auto"><span class="autocomment">Asymptotic complexity of an algorithm</span></span></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 19:40, 24 April 2016</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l21">Line 21:</td> <td colspan="2" class="diff-lineno">Line 21:</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>## In the '''best case''': by the function <math>f_\min:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f_{\min}(n_1,\ldots,n_k)</math> is the ''minimum'' number of operations executed by the algorithm for any instance in <math>\mathcal{I}(n_1,\ldots,n_k)</math>.</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>## In the '''best case''': by the function <math>f_\min:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f_{\min}(n_1,\ldots,n_k)</math> is the ''minimum'' number of operations executed by the algorithm for any instance in <math>\mathcal{I}(n_1,\ldots,n_k)</math>.</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;"><div>## In the '''average case''': For this case, a [http://en.wikipedia.org/wiki/Probability_distribution probability distribution] <math>P_{n_1,\ldots,n_k}</math> over each set <math>\mathcal{I}(n_1,\ldots,n_k)</math> is required. For short, let <math>P:=(P_{n_1,\ldots,n_k})_{n_1,\ldots,n_k\in\mathbb{N}}</math>. Then the asymptotic average complexity is the function <math>f_P:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f_P(n_1,\ldots,n_k)</math> is the ''expected'' number of operations executed by the algorithm, taken over all instances in <math>\mathcal{I}(n_1,\ldots,n_k)</math>, with respect to the distribution <math>P_{n_1,\ldots,n_k}</math>.</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>## In the '''average case''': For this case, a [http://en.wikipedia.org/wiki/Probability_distribution probability distribution] <math>P_{n_1,\ldots,n_k}</math> over each set <math>\mathcal{I}(n_1,\ldots,n_k)</math> is required. For short, let <math>P:=(P_{n_1,\ldots,n_k})_{n_1,\ldots,n_k\in\mathbb{N}}</math>. Then the asymptotic average complexity is the function <math>f_P:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f_P(n_1,\ldots,n_k)</math> is the ''expected'' number of operations executed by the algorithm, taken over all instances in <math>\mathcal{I}(n_1,\ldots,n_k)</math>, with respect to the distribution <math>P_{n_1,\ldots,n_k}</math>.</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;">'''Remark:'''</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><ins style="font-weight: bold; text-decoration: none;">An asymptotic complexity analysis of an algorithm combines two aspects: which case (worst, best, average) and which [[Asymptotic comparison of functions|function class]] (<math>\mathcal{O}</math>, <math>\Omega</math>, <math>\Theta<math>, <math>o</math>. Note that the case and the function class are two separate concepts, which are frequently confused.</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"></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>== Bounds on the asymtptotic complexity ==</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>== Bounds on the asymtptotic complexity ==</div></td></tr> </table>

Weihe https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Asymptotic_complexity_of_algorithms&diff=3805&oldid=prev Weihe: /* Asymptotic complexity of an algorithm */ 2016-04-24T19:29:07Z

<p><span dir="auto"><span class="autocomment">Asymptotic complexity of an algorithm</span></span></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 19:29, 24 April 2016</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l16">Line 16:</td> <td colspan="2" class="diff-lineno">Line 16:</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>== Asymptotic complexity of an algorithm ==</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>== Asymptotic complexity of an algorithm ==</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># For a selection of <math>k</math> characterizing parameters for an [[Algorithms and correctness#Algorithmic problem|algorithmic problem]], let <math>\mathcal{I}(n_1,\ldots,n_k)</math> denote the set of all [Algorithms and correctness#Algorithmic problem|instances] for which these parameters assume the values <math>n_1,\ldots,n_k</math>.</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># For a selection of <math>k</math> characterizing parameters for an [[Algorithms and correctness#Algorithmic problem|algorithmic problem]], let <math>\mathcal{I}(n_1,\ldots,n_k)</math> denote the set of all <ins style="font-weight: bold; text-decoration: none;">[</ins>[Algorithms and correctness#Algorithmic problem|instances<ins style="font-weight: bold; text-decoration: none;">]</ins>] for which these parameters assume the values <math>n_1,\ldots,n_k</math>.</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;"><div># For an [[Algorithms and correctness#Algorithm|algorithm]] for this algorithmic problem, the '''asymptotic complexity''' of the algorithm with respect to this selection of characterizing parameters is defined as follows.</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># For an [[Algorithms and correctness#Algorithm|algorithm]] for this algorithmic problem, the '''asymptotic complexity''' of the algorithm with respect to this selection of characterizing parameters is defined as follows.</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;"><div>## In the '''worst case''': by the function <math>f_\max:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f_{\max} (n_1,\ldots,n_k)</math> is the ''maximum'' number of operations executed by the algorithm for any instance in <math>\mathcal{I}(n_1,\ldots,n_k)</math>.</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>## In the '''worst case''': by the function <math>f_\max:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f_{\max} (n_1,\ldots,n_k)</math> is the ''maximum'' number of operations executed by the algorithm for any instance in <math>\mathcal{I}(n_1,\ldots,n_k)</math>.</div></td></tr> </table>

Weihe https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Asymptotic_complexity_of_algorithms&diff=3804&oldid=prev Weihe: /* Asymptotic complexity of an algorithm */ 2016-04-24T19:28:24Z

<p><span dir="auto"><span class="autocomment">Asymptotic complexity of an algorithm</span></span></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 19:28, 24 April 2016</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l16">Line 16:</td> <td colspan="2" class="diff-lineno">Line 16:</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>== Asymptotic complexity of an algorithm ==</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>== Asymptotic complexity of an algorithm ==</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># For a selection of <math>k</math> characterizing parameters for an [[Algorithms and correctness#Algorithmic problem|algorithmic problem]], let <math>\mathcal{I}(n_1,\ldots,n_k)</math> denote the set of all instances for which these parameters assume the values <math>n_1,\ldots,n_k</math>.</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># For a selection of <math>k</math> characterizing parameters for an [[Algorithms and correctness#Algorithmic problem|algorithmic problem]], let <math>\mathcal{I}(n_1,\ldots,n_k)</math> denote the set of all <ins style="font-weight: bold; text-decoration: none;">[Algorithms and correctness#Algorithmic problem|</ins>instances<ins style="font-weight: bold; text-decoration: none;">] </ins>for which these parameters assume the values <math>n_1,\ldots,n_k</math>.</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;"><div># For an [[Algorithms and correctness#Algorithm|algorithm]] for this algorithmic problem, the '''asymptotic complexity''' of the algorithm with respect to this selection of characterizing parameters is defined as follows.</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># For an [[Algorithms and correctness#Algorithm|algorithm]] for this algorithmic problem, the '''asymptotic complexity''' of the algorithm with respect to this selection of characterizing parameters is defined as follows.</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;"><div>## In the '''worst case''': by the function <math>f_\max:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f_{\max} (n_1,\ldots,n_k)</math> is the ''maximum'' number of operations executed by the algorithm for any instance in <math>\mathcal{I}(n_1,\ldots,n_k)</math>.</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>## In the '''worst case''': by the function <math>f_\max:\mathbb{N}^k\rightarrow\mathbb{R}^+</math> such that <math>f_{\max} (n_1,\ldots,n_k)</math> is the ''maximum'' number of operations executed by the algorithm for any instance in <math>\mathcal{I}(n_1,\ldots,n_k)</math>.</div></td></tr> </table>

Weihe https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Asymptotic_complexity_of_algorithms&diff=3802&oldid=prev Weihe: /* Asymptotic complexity vs. run time */ 2016-04-24T19:25:45Z

<p><span dir="auto"><span class="autocomment">Asymptotic complexity vs. run time</span></span></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 19:25, 24 April 2016</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l3">Line 3:</td> <td colspan="2" class="diff-lineno">Line 3:</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>== Asymptotic complexity vs. run time ==</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>== Asymptotic complexity vs. run time ==</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># Roughly speaking, the run time of an algorithm is measured by the number of [[Algorithms and correctness#<del style="font-weight: bold; text-decoration: none;">Operations and instructions|</del>Instructions, operations and subroutines]] executed by the machine.</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># Roughly speaking, the run time of an algorithm is measured by the number of [[Algorithms and correctness#Instructions, operations and subroutines<ins style="font-weight: bold; text-decoration: none;">|operations</ins>]] executed by the machine.</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;"><div># However, in theoretical considerations, the run time is estimated by the algorithm's '''asymptotic complexity'''. In [[Asymptotic comparison of functions|asymptotic]] considerations, constant multiplicative factors are completely disregarded. For that, it does not matter how fast the machine and how smart the algorithm's implementation is.</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># However, in theoretical considerations, the run time is estimated by the algorithm's '''asymptotic complexity'''. In [[Asymptotic comparison of functions|asymptotic]] considerations, constant multiplicative factors are completely disregarded. For that, it does not matter how fast the machine and how smart the algorithm's implementation is.</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> </table>

Weihe https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Asymptotic_complexity_of_algorithms&diff=3800&oldid=prev Weihe: /* Asymptotic complexity vs. run time */ 2016-04-24T19:24:36Z

<p><span dir="auto"><span class="autocomment">Asymptotic complexity vs. run time</span></span></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 19:24, 24 April 2016</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l3">Line 3:</td> <td colspan="2" class="diff-lineno">Line 3:</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>== Asymptotic complexity vs. run time ==</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>== Asymptotic complexity vs. run time ==</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># Roughly speaking, the run time of an algorithm is measured by the number of [[Algorithms and correctness#Operations and instructions|operations]] executed by the machine.</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># Roughly speaking, the run time of an algorithm is measured by the number of [[Algorithms and correctness#Operations and instructions|<ins style="font-weight: bold; text-decoration: none;">Instructions, </ins>operations <ins style="font-weight: bold; text-decoration: none;">and subroutines</ins>]] executed by the machine.</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;"><div># However, in theoretical considerations, the run time is estimated by the algorithm's '''asymptotic complexity'''. In [[Asymptotic comparison of functions|asymptotic]] considerations, constant multiplicative factors are completely disregarded. For that, it does not matter how fast the machine and how smart the algorithm's implementation is.</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># However, in theoretical considerations, the run time is estimated by the algorithm's '''asymptotic complexity'''. In [[Asymptotic comparison of functions|asymptotic]] considerations, constant multiplicative factors are completely disregarded. For that, it does not matter how fast the machine and how smart the algorithm's implementation is.</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> </table>

Weihe