In
computational complexity theory, asymptotic computational complexity is the usage of
asymptotic analysis
In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior.
As an illustration, suppose that we are interested in the properties of a function as becomes very large. If , then as beco ...
for the estimation of computational complexity of
algorithms and
computational problems, commonly associated with the usage of the
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 Paul Bachmann, Edmund Lan ...
.
Scope
With respect to
computational resources, asymptotic
time complexity and asymptotic
space complexity are commonly estimated. Other asymptotically estimated behavior include
circuit complexity and various measures of
parallel computation, such as the number of (parallel) processors.
Since the ground-breaking 1965 paper by
Juris Hartmanis and
Richard E. Stearns and the 1979 book by
Michael Garey and
David S. Johnson on
NP-completeness,
[ Michael Garey, and David S. Johnson: ''Computers and Intractability: A Guide to the Theory of NP-Completeness.'' New York: W. H. Freeman & Co., 1979.] the term "
computational complexity
In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...
" (of algorithms) has become commonly referred to as asymptotic computational complexity.
Further, unless specified otherwise, the term "computational complexity" usually refers to the
upper bound for the asymptotic computational complexity of an algorithm or a problem, which is usually written in terms of the big O notation, e.g..
Other types of (asymptotic) computational complexity estimates are
lower bounds ("
Big Omega" notation; e.g., Ω(''n'')) and asymptotically tight estimates, when the asymptotic upper and lower bounds coincide (written using the "
big Theta"; e.g., Θ(''n'' log ''n'')).
A further
tacit assumption is that the
worst case analysis of computational complexity is in question unless stated otherwise. An alternative approach is
probabilistic analysis of algorithms
Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speaking ...
.
Types of algorithms considered
In most practical cases
deterministic algorithms or
randomized algorithm
A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...
s are discussed, although
theoretical computer science also considers
nondeterministic algorithm
In computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There are several ways an algorithm may behave diffe ...
s and other advanced
models of computation.
See also
*
Asymptotically optimal algorithm
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 en ...
References
{{reflist
Computational complexity theory