computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

, asymptotic computational complexity is the usage of

asymptotic analysis In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing Limit (mathematics), limiting behavior. As an illustration, suppose that we are interested in the properties of a function as becomes very larg ...

for the estimation of computational complexity of

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 ...

s and

computational problem In theoretical computer science, a computational problem is one that asks for a solution in terms of an algorithm. For example, the problem of factoring :"Given a positive integer ''n'', find a nontrivial prime factor of ''n''." is a computati ...

s, commonly associated with the usage of the

big O notation Big ''O'' notation is a mathematical notation that describes the asymptotic analysis, limiting behavior of a function (mathematics), function when the Argument of a function, argument tends towards a particular value or infinity. Big O is a memb ...

Scope

With respect to computational resources, asymptotic

time complexity In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...

and asymptotic

space complexity The space complexity of an algorithm or a data structure is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it exec ...

of computational algorithms and programs are commonly estimated. Other asymptotically estimated behavior include

circuit complexity In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circui ...

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 In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

, 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 In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is every element of . Dually, a lower bound or minorant of is defined to be an element of that is less ...

for the asymptotic computational complexity of an algorithm or a problem, which is usually written in terms of the big O notation, e.g..

O(n^3).

Other types of (asymptotic) computational complexity estimates are

lower bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is every element of . Dually, a lower bound or minorant of is defined to be an element of that is less th ...

s (" 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 A tacit assumption or implicit assumption is an assumption that underlies a logical argument, course of action, Decision-making, decision, or judgment that is not explicitly voiced nor necessarily understood by the decision maker or judge. These as ...

is that the worst case analysis of computational complexity is in question unless stated otherwise. An alternative approach is

probabilistic analysis of algorithms In analysis of algorithms, probabilistic analysis of algorithms is an approach to estimate the computational complexity of an algorithm or a computational problem. It starts from an assumption about a probabilistic distribution of the set of all pos ...

Types of algorithms considered

In most practical cases

deterministic algorithm In computer science, a deterministic algorithm is an algorithm that, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. Deterministic algorithms are by fa ...

s 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 Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...

also considers

nondeterministic algorithm In computer science and 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. Different models of computation ...

s and other advanced

models 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 ...

References

{{reflist Computational complexity theory

Scope

Types of algorithms considered

See also

References