Asymptotically optimal algorithm
   HOME

TheInfoList



OR:

In
computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
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 Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by German mathematicians Pau ...
. More formally, an algorithm is asymptotically optimal with respect to a particular
resource ''Resource'' refers to all the materials available in our environment which are Technology, technologically accessible, Economics, economically feasible and Culture, culturally Sustainability, sustainable and help us to satisfy our needs and want ...
if the problem has been proven to require of that resource, and the algorithm has been proven to use only These proofs require an assumption of a particular
model of computation In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how an output of a mathematical function is computed given an input. A model describes how ...
, i.e., certain restrictions on operations allowable with the input data. As a simple example, it's known that all
comparison sort A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should oc ...
s require at least comparisons in the average and worst cases.
Mergesort In computer science, merge sort (also commonly spelled as mergesort and as ) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations of merge sort are stable, which means that the relative order of equal el ...
and
heapsort In computer science, heapsort is an efficient, comparison-based sorting algorithm that reorganizes an input array into a heap (a data structure where each node is greater than its children) and then repeatedly removes the largest node from that ...
are comparison sorts which perform comparisons, so they are asymptotically optimal in this sense. If the input data have some ''
a priori ('from the earlier') and ('from the later') are Latin phrases used in philosophy to distinguish types of knowledge, Justification (epistemology), justification, or argument by their reliance on experience. knowledge is independent from any ...
'' 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 objects are
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
s from the range then they may be sorted 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. In practice it's useful to find algorithms that perform better, even if they do not enjoy any asymptotic advantage. New algorithms may also present advantages such as better performance on specific inputs, decreased use of resources, or being simpler to describe and implement. Thus asymptotically optimal algorithms are not always the "end of the line". 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 beyond the range of practical input sizes, such as inputs with more
bit The bit is the most basic unit of information in computing and digital communication. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represented as ...
s than could fit in any 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. * The inputs encountered in practice fall into
special case In logic, especially as applied in mathematics, concept is a special case or specialization of concept precisely if every instance of is also an instance of but not vice versa, or equivalently, if is a generalization of .Brown, James Robert.� ...
s that have more efficient algorithms or that
heuristic algorithms A heuristic or heuristic technique (''problem solving'', '' mental shortcut'', ''rule of thumb'') is any approach to problem solving that employs a pragmatic method that is not fully optimized, perfected, or rationalized, but is nevertheless ...
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. An example of an asymptotically optimal algorithm not used in practice is Bernard Chazelle's linear-time algorithm for
triangulation In trigonometry and geometry, triangulation is the process of determining the location of a point by forming triangles to the point from known points. Applications In surveying Specifically in surveying, triangulation involves only angle m ...
of a
simple polygon In geometry, a simple polygon is a polygon that does not Intersection (Euclidean geometry), intersect itself and has no holes. That is, it is a Piecewise linear curve, piecewise-linear Jordan curve consisting of finitely many line segments. The ...
. Another is the resizable array data structure published in "Resizable Arrays in Optimal Time and Space", which can index in constant time but on many machines carries a heavy practical penalty compared to ordinary array indexing.


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 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: :\lim_ \frac < \infty. 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. Sometimes vague or implicit assumptions can make it unclear whether an algorithm is asymptotically optimal. For example, a lower bound theorem might assume a particular
abstract machine In computer science, an abstract machine is a theoretical model that allows for a detailed and precise analysis of how a computer system functions. It is similar to a mathematical function in that it receives inputs and produces outputs based on p ...
model, as in the case of comparison sorts, or a particular organization of memory. By violating these assumptions, a new algorithm could potentially asymptotically outperform the lower bound and the "asymptotically optimal" algorithms.


Speedup

The nonexistence of an asymptotically optimal algorithm is called speedup.
Blum's speedup theorem In computational complexity theory, Blum's speedup theorem, first stated by Manuel Blum in 1967, is a fundamental theorem about the complexity of computable functions. Each computable function has an infinite number of different program representa ...
shows that there exist artificially constructed problems with speedup. However, it is an
open problem In science and mathematics, an open problem or an open question is a known problem which can be accurately stated, and which is assumed to have an objective and verifiable solution, but which has not yet been solved (i.e., no solution for it is kno ...
whether many of the most well-known algorithms today are asymptotically optimal or not. For example, there is an O(n\alpha(n)) algorithm for finding
minimum spanning tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. ...
s, where \alpha(n) is the very slowly growing inverse of the
Ackermann function In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total function, total computable function that is not Primitive recursive function, primitive recursive. ...
, but the best known lower bound is the trivial \Omega(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).


See also

*
Element uniqueness problem In computational complexity theory, the element distinctness problem or element uniqueness problem is the problem of determining whether all the elements of a list are distinct. It is a well studied problem in many different models of computation. ...
* Asymptotic computational complexity


References

{{Reflist Analysis of algorithms