Asymptotically optimal algorithm - Revision history

HeyElliott: /* Formal definitions */ MOS:NOTE

2023-08-26T21:33:14Z

Formal definitions: MOS:NOTE

← Previous revision		Revision as of 21:33, 26 August 2023
Line 45:		Line 45:
	:<math>\lim_{n\rightarrow\infty} \frac{t(n)}{b(n)} < \infty.</math>		:<math>\lim_{n\rightarrow\infty} \frac{t(n)}{b(n)} < \infty.</math>

	~~Note that this~~ limit, if it exists, is always at least 1, as t(''n'') ≥ b(''n'').		This limit, if it exists, is always at least 1, as t(''n'') ≥ b(''n'').

	Although usually applied to time efficiency, an algorithm can be said to use asymptotically optimal space, random bits, number of processors, or any other resource commonly measured using big-O notation.		Although usually applied to time efficiency, an algorithm can be said to use asymptotically optimal space, random bits, number of processors, or any other resource commonly measured using big-O notation.

Beland: fix link (via WP:JWB)

2023-08-19T03:19:17Z

fix link (via WP:JWB)

← Previous revision		Revision as of 03:19, 19 August 2023
Line 41:		Line 41:

	==Formal definitions==		==Formal definitions==
	Formally, suppose that we have a lower-bound theorem showing that a problem requires Ω(f(''n'')) time to solve for an instance (input) of size ''n'' (see ~~[[big-O~~ ~~notation#Other~~ ~~standard computer science~~ notation: ~~Ω, ω, Θ, O, o, Õ, ∼\|big-O~~ notation]] for the definition of Ω). Then, an algorithm which solves the problem in O(f(''n'')) time is said to be asymptotically optimal. This can also be expressed using limits: suppose that b(''n'') is a lower bound on the running time, and a given algorithm takes time t(''n''). Then the algorithm is asymptotically optimal if:		Formally, suppose that we have a lower-bound theorem showing that a problem requires Ω(f(''n'')) time to solve for an instance (input) of size ''n'' (see {{section link\|Big O notation\|Big Omega notation}} for the definition of Ω). Then, an algorithm which solves the problem in O(f(''n'')) time is said to be asymptotically optimal. This can also be expressed using limits: suppose that b(''n'') is a lower bound on the running time, and a given algorithm takes time t(''n''). Then the algorithm is asymptotically optimal if:

	:<math>\lim_{n\rightarrow\infty} \frac{t(n)}{b(n)} < \infty.</math>		:<math>\lim_{n\rightarrow\infty} \frac{t(n)}{b(n)} < \infty.</math>

Sungodtemple: /* Speedup */ convert to math tags

2023-05-27T02:22:34Z

Speedup: convert to math tags

← Previous revision		Revision as of 02:22, 27 May 2023
Line 52:		Line 52:

	==Speedup==		==Speedup==
	The nonexistence of an asymptotically optimal algorithm is called speedup. [[Blum's speedup theorem]] shows that there exist artificially constructed problems with speedup. However, it is an [[open problem]] whether many of the most well-known algorithms today are asymptotically optimal or not. For example, there is an O(''n~~''α~~(''n'')) algorithm for finding [[minimum spanning tree]]s, where α(''n'') is the very slowly growing inverse of the [[Ackermann function]], but the best known lower bound is the trivial Ω(''n''). Whether this algorithm is asymptotically optimal is unknown, and would be likely to be hailed as a significant result if it were resolved either way. Coppersmith and Winograd (1982) proved that matrix multiplication has a weak form of speed-up among a restricted class of algorithms (Strassen-type bilinear identities with lambda-computation).		The nonexistence of an asymptotically optimal algorithm is called speedup. [[Blum's speedup theorem]] shows that there exist artificially constructed problems with speedup. However, it is an [[open problem]] whether many of the most well-known algorithms today are asymptotically optimal or not. For example, there is an <math>O(n\alpha(n))</math> algorithm for finding [[minimum spanning tree]]s, where <math>\alpha(n)</math> is the very slowly growing inverse of the [[Ackermann function]], but the best known lower bound is the trivial <math>\Omega(n)</math>. Whether this algorithm is asymptotically optimal is unknown, and would be likely to be hailed as a significant result if it were resolved either way. Coppersmith and Winograd (1982) proved that matrix multiplication has a weak form of speed-up among a restricted class of algorithms (Strassen-type bilinear identities with lambda-computation).

	==See also==		==See also==

Dragonflare82: Fixed triangulation link which was pointing to wrong interpretation of "triangulation" (location identification instead of subdivision)

2023-02-28T08:47:35Z

Fixed triangulation link which was pointing to wrong interpretation of "triangulation" (location identification instead of subdivision)

← Previous revision		Revision as of 08:47, 28 February 2023
Line 22:		Line 22:
	* On modern computers, [[Computer hardware\|hardware]] optimizations such as [[memory cache]] and [[Parallel computing\|parallel processing]] may be "broken" by an asymptotically optimal algorithm (assuming the analysis did not take these hardware optimizations into account). In this case, there could be sub-optimal algorithms that make better use of these features and outperform an optimal algorithm on realistic data.		* On modern computers, [[Computer hardware\|hardware]] optimizations such as [[memory cache]] and [[Parallel computing\|parallel processing]] may be "broken" by an asymptotically optimal algorithm (assuming the analysis did not take these hardware optimizations into account). In this case, there could be sub-optimal algorithms that make better use of these features and outperform an optimal algorithm on realistic data.

	An example of an asymptotically optimal algorithm not used in practice is [[Bernard Chazelle]]'s [[linear-time]] algorithm for [[triangulation]] of a [[simple polygon]]. Another is the [[resizable array]] data structure published in "Resizable Arrays in Optimal Time and Space",<ref>{{Citation		An example of an asymptotically optimal algorithm not used in practice is [[Bernard Chazelle]]'s [[linear-time]] algorithm for [[Polygon triangulation\|triangulation]] of a [[simple polygon]]. Another is the [[resizable array]] data structure published in "Resizable Arrays in Optimal Time and Space",<ref>{{Citation
	\| title=Resizable Arrays in Optimal Time and Space		\| title=Resizable Arrays in Optimal Time and Space
	\| url=http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf		\| url=http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf

OlliverWithDoubleL: Fixed link

2022-06-05T05:56:15Z

Fixed link

← Previous revision		Revision as of 05:56, 5 June 2022
Line 20:		Line 20:
	* It is too complex, so that the difficulty of comprehending and implementing it correctly outweighs its potential benefit in the range of input sizes under consideration.		* It is too complex, so that the difficulty of comprehending and implementing it correctly outweighs its potential benefit in the range of input sizes under consideration.
	* The inputs encountered in practice fall into [[special case]]s that have more efficient algorithms or that [[Heuristic (computer science)\|heuristic algorithms]] with bad worst-case times can nevertheless solve efficiently.		* The inputs encountered in practice fall into [[special case]]s that have more efficient algorithms or that [[Heuristic (computer science)\|heuristic algorithms]] with bad worst-case times can nevertheless solve efficiently.
	* On modern computers, [[Computer hardware\|hardware]] optimizations such as [[memory cache]] and [[parallel processing]] may be "broken" by an asymptotically optimal algorithm (assuming the analysis did not take these hardware optimizations into account). In this case, there could be sub-optimal algorithms that make better use of these features and outperform an optimal algorithm on realistic data.		* On modern computers, [[Computer hardware\|hardware]] optimizations such as [[memory cache]] and [[Parallel computing\|parallel processing]] may be "broken" by an asymptotically optimal algorithm (assuming the analysis did not take these hardware optimizations into account). In this case, there could be sub-optimal algorithms that make better use of these features and outperform an optimal algorithm on realistic data.

	An example of an asymptotically optimal algorithm not used in practice is [[Bernard Chazelle]]'s [[linear-time]] algorithm for [[triangulation]] of a [[simple polygon]]. Another is the [[resizable array]] data structure published in "Resizable Arrays in Optimal Time and Space",<ref>{{Citation		An example of an asymptotically optimal algorithm not used in practice is [[Bernard Chazelle]]'s [[linear-time]] algorithm for [[triangulation]] of a [[simple polygon]]. Another is the [[resizable array]] data structure published in "Resizable Arrays in Optimal Time and Space",<ref>{{Citation

OlliverWithDoubleL: Fixed typo

2022-06-05T05:55:01Z

Fixed typo

← Previous revision		Revision as of 05:55, 5 June 2022
Line 4:		Line 4:
	In [[computer science]], an [[algorithm]] is said to be '''asymptotically optimal''' if, roughly speaking, for large inputs it performs [[Best, worst and average case\|at worst]] a constant factor (independent of the input size) worse than the best possible algorithm. It is a term commonly encountered in computer science research as a result of widespread use of [[big-O notation]].		In [[computer science]], an [[algorithm]] is said to be '''asymptotically optimal''' if, roughly speaking, for large inputs it performs [[Best, worst and average case\|at worst]] a constant factor (independent of the input size) worse than the best possible algorithm. It is a term commonly encountered in computer science research as a result of widespread use of [[big-O notation]].

	More formally, an algorithm is asymptotically optimal with respect to a particular [[System resource\|resource]] if the problem has been proven to require {{math\|Ω(f(''n''))}} of that resource, and the algorithm has been proven to use only {{math\|O(f(''n'')).}}		More formally, an algorithm is asymptotically optimal with respect to a particular [[System resource\|resource]] if the problem has been proven to require {{math\|Ω(''f''(''n''))}} of that resource, and the algorithm has been proven to use only {{math\|O(''f''(''n'')).}}

	These proofs require an assumption of a particular [[model of computation]], i.e., certain restrictions on operations allowable with the input data.		These proofs require an assumption of a particular [[model of computation]], i.e., certain restrictions on operations allowable with the input data.

OlliverWithDoubleL: added short description, links

2022-06-05T05:53:56Z

added short description, links

Beland: convert special characters (via WP:JWB)

2020-05-25T07:58:30Z

convert special characters (via WP:JWB)

← Previous revision		Revision as of 07:58, 25 May 2020
Line 40:		Line 40:

	==Formal definitions==		==Formal definitions==
	Formally, suppose that we have a lower-bound theorem showing that a problem requires Ω(f(''n'')) time to solve for an instance (input) of size ''n'' (see [[big-O notation#Other standard computer science notation: Ω, ω, Θ, O, o, Õ, ~~&sim;~~\|big-O notation]] for the definition of Ω). Then, an algorithm which solves the problem in O(f(''n'')) time is said to be asymptotically optimal. This can also be expressed using limits: suppose that b(''n'') is a lower bound on the running time, and a given algorithm takes time t(''n''). Then the algorithm is asymptotically optimal if:		Formally, suppose that we have a lower-bound theorem showing that a problem requires Ω(f(''n'')) time to solve for an instance (input) of size ''n'' (see [[big-O notation#Other standard computer science notation: Ω, ω, Θ, O, o, Õ, ∼\|big-O notation]] for the definition of Ω). Then, an algorithm which solves the problem in O(f(''n'')) time is said to be asymptotically optimal. This can also be expressed using limits: suppose that b(''n'') is a lower bound on the running time, and a given algorithm takes time t(''n''). Then the algorithm is asymptotically optimal if:

	:<math>\lim_{n\rightarrow\infty} \frac{t(n)}{b(n)} < \infty.</math>		:<math>\lim_{n\rightarrow\infty} \frac{t(n)}{b(n)} < \infty.</math>

Alanhuang122: removing nonsensical date citation field

2017-06-19T15:59:31Z

removing nonsensical date citation field

← Previous revision		Revision as of 15:59, 19 June 2017
Line 23:		Line 23:
	An example of an asymptotically optimal algorithm not used in practice is [[Bernard Chazelle]]'s linear-time algorithm for [[triangulation]] of a [[simple polygon]]. Another is the [[resizable array]] data structure published in "Resizable Arrays in Optimal Time and Space",<ref>{{Citation		An example of an asymptotically optimal algorithm not used in practice is [[Bernard Chazelle]]'s linear-time algorithm for [[triangulation]] of a [[simple polygon]]. Another is the [[resizable array]] data structure published in "Resizable Arrays in Optimal Time and Space",<ref>{{Citation
	\| title=Resizable Arrays in Optimal Time and Space		\| title=Resizable Arrays in Optimal Time and Space
	\| date=Technical Report CS-99-09
	\| url=http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf		\| url=http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf
	\| year=1999		\| year=1999

Meng6 at 03:10, 28 October 2013

2013-10-28T03:10:12Z

← Previous revision		Revision as of 03:10, 28 October 2013
Line 9:		Line 9:
	As a simple example, it's known that all [[comparison sort]]s require at least Ω(''n'' log ''n'') comparisons in the average and worst cases. [[Mergesort]] and [[heapsort]] are comparison sorts which perform O(''n'' log ''n'') comparisons, so they are asymptotically optimal in this sense.		As a simple example, it's known that all [[comparison sort]]s require at least Ω(''n'' log ''n'') comparisons in the average and worst cases. [[Mergesort]] and [[heapsort]] are comparison sorts which perform O(''n'' log ''n'') comparisons, so they are asymptotically optimal in this sense.

	If the input data have some ''a priori'' properties which can be exploited in construction of algorithms, in addition to comparisons, then asymptotically faster algorithms may be possible. For example, if it is known that the N objects are [[integer]]s from the range [1..N], then they may be sorted O(N) time, e.g., by the [[bucket sort]].		If the input data have some ''[[a priori and a posteriori\|a priori]]'' properties which can be exploited in construction of algorithms, in addition to comparisons, then asymptotically faster algorithms may be possible. For example, if it is known that the N objects are [[integer]]s from the range [1, N], then they may be sorted O(N) time, e.g., by the [[bucket sort]].

	A consequence of an algorithm being asymptotically optimal is that, for large enough inputs, no algorithm can outperform it by more than a constant factor. For this reason, asymptotically optimal algorithms are often seen as the "end of the line" in research, the attaining of a result that cannot be dramatically improved upon. Conversely, if an algorithm is not asymptotically optimal, this implies that as the input grows in size, the algorithm performs increasingly worse than the best possible algorithm.		A consequence of an algorithm being asymptotically optimal is that, for large enough inputs, no algorithm can outperform it by more than a constant factor. For this reason, asymptotically optimal algorithms are often seen as the "end of the line" in research, the attaining of a result that cannot be dramatically improved upon. Conversely, if an algorithm is not asymptotically optimal, this implies that as the input grows in size, the algorithm performs increasingly worse than the best possible algorithm.

← Previous revision		Revision as of 05:53, 5 June 2022
Line 1:		Line 1:
			{{Short description\|Measure of algorithm performance for large inputs}}
	{{Refimprove\|date=October 2008}}		{{Refimprove\|date=October 2008}}

	In [[computer science]], an [[algorithm]] is said to be '''asymptotically optimal''' if, roughly speaking, for large inputs it performs at worst a constant factor (independent of the input size) worse than the best possible algorithm. It is a term commonly encountered in computer science research as a result of widespread use of [[big-O notation]].		In [[computer science]], an [[algorithm]] is said to be '''asymptotically optimal''' if, roughly speaking, for large inputs it performs [[Best, worst and average case\|at worst]] a constant factor (independent of the input size) worse than the best possible algorithm. It is a term commonly encountered in computer science research as a result of widespread use of [[big-O notation]].

	More formally, an algorithm is asymptotically optimal with respect to a particular resource if the problem has been proven to require Ω(f(n)) of that resource, and the algorithm has been proven to use only O(f(n)).		More formally, an algorithm is asymptotically optimal with respect to a particular [[System resource\|resource]] if the problem has been proven to require {{math\|Ω(f(''n''))}} of that resource, and the algorithm has been proven to use only {{math\|O(f(''n'')).}}

	These proofs require an assumption of a particular [[model of computation]], i.e., certain restrictions on operations allowable with the input data.		These proofs require an assumption of a particular [[model of computation]], i.e., certain restrictions on operations allowable with the input data.

	As a simple example, it's known that all [[comparison sort]]s require at least Ω(''n'' log ''n'') comparisons in the average and worst cases. [[Mergesort]] and [[heapsort]] are comparison sorts which perform O(''n'' log ''n'') comparisons, so they are asymptotically optimal in this sense.		As a simple example, it's known that all [[comparison sort]]s require at least {{math\|Ω(''n'' log ''n'')}} comparisons in the average and worst cases. [[Mergesort]] and [[heapsort]] are comparison sorts which perform {{math\|O(''n'' log ''n'')}} comparisons, so they are asymptotically optimal in this sense.

	If the input data have some ''[[a priori and a posteriori\|a priori]]'' properties which can be exploited in construction of algorithms, in addition to comparisons, then asymptotically faster algorithms may be possible. For example, if it is known that the N objects are [[integer]]s from the range [1, N], then they may be sorted O(N) time, e.g., by the [[bucket sort]].		If the input data have some ''[[a priori and a posteriori\|a priori]]'' properties which can be exploited in construction of algorithms, in addition to comparisons, then asymptotically faster algorithms may be possible. For example, if it is known that the {{mvar\|N}} objects are [[integer]]s from the range {{math\|[1, ''N''],}} then they may be sorted {{math\|O(''N'')}} time, e.g., by the [[bucket sort]].

	A consequence of an algorithm being asymptotically optimal is that, for large enough inputs, no algorithm can outperform it by more than a constant factor. For this reason, asymptotically optimal algorithms are often seen as the "end of the line" in research, the attaining of a result that cannot be dramatically improved upon. Conversely, if an algorithm is not asymptotically optimal, this implies that as the input grows in size, the algorithm performs increasingly worse than the best possible algorithm.		A consequence of an algorithm being asymptotically optimal is that, for large enough inputs, no algorithm can outperform it by more than a constant factor. For this reason, asymptotically optimal algorithms are often seen as the "end of the line" in research, the attaining of a result that cannot be dramatically improved upon. Conversely, if an algorithm is not asymptotically optimal, this implies that as the input grows in size, the algorithm performs increasingly worse than the best possible algorithm.
Line 16:		Line 17:

	Although asymptotically optimal algorithms are important theoretical results, an asymptotically optimal algorithm might not be used in a number of practical situations:		Although asymptotically optimal algorithms are important theoretical results, an asymptotically optimal algorithm might not be used in a number of practical situations:
	* It only outperforms more commonly used methods for ''n'' beyond the range of practical input sizes, such as inputs with more ~~bits~~ than could fit in any computer storage system.		* It only outperforms more commonly used methods for {{mvar\|n}} beyond the range of practical input sizes, such as inputs with more [[bit]]s than could fit in any [[Computer data storage\|computer storage system]].
	* It is too complex, so that the difficulty of comprehending and implementing it correctly outweighs its potential benefit in the range of input sizes under consideration.		* It is too complex, so that the difficulty of comprehending and implementing it correctly outweighs its potential benefit in the range of input sizes under consideration.
	* The inputs encountered in practice fall into special ~~cases~~ that have more efficient algorithms or that heuristic algorithms with bad worst-case times can nevertheless solve efficiently.		* The inputs encountered in practice fall into [[special case]]s that have more efficient algorithms or that [[Heuristic (computer science)\|heuristic algorithms]] with bad worst-case times can nevertheless solve efficiently.
	* On modern computers, hardware optimizations such as memory cache and parallel processing may be "broken" by an asymptotically optimal algorithm (assuming the analysis did not take these hardware optimizations into account). In this case, there could be sub-optimal algorithms that make better use of these features and outperform an optimal algorithm on realistic data.		* On modern computers, [[Computer hardware\|hardware]] optimizations such as [[memory cache]] and [[parallel processing]] may be "broken" by an asymptotically optimal algorithm (assuming the analysis did not take these hardware optimizations into account). In this case, there could be sub-optimal algorithms that make better use of these features and outperform an optimal algorithm on realistic data.

	An example of an asymptotically optimal algorithm not used in practice is [[Bernard Chazelle]]'s linear-time algorithm for [[triangulation]] of a [[simple polygon]]. Another is the [[resizable array]] data structure published in "Resizable Arrays in Optimal Time and Space",<ref>{{Citation		An example of an asymptotically optimal algorithm not used in practice is [[Bernard Chazelle]]'s [[linear-time]] algorithm for [[triangulation]] of a [[simple polygon]]. Another is the [[resizable array]] data structure published in "Resizable Arrays in Optimal Time and Space",<ref>{{Citation
	\| title=Resizable Arrays in Optimal Time and Space		\| title=Resizable Arrays in Optimal Time and Space
	\| url=http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf		\| url=http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf