Asymptotic computational complexity

From Wikipedia, the free encyclopedia

In computational complexity theory, asymptotic computational complexity is the usage of the asymptotic analysis for the estimation of computational complexity of algorithms and computational problems, commonly associated with the usage of the big O notation.

In terms of the most commonly estimated computational resources, it is spoken about the asymptotic time complexity and asymptotic space complexity. Other asymptotically estimated resources include circuit complexity and various measures of parallel computation, such as the number of (parallel) processors.

Since the groundlaying 1965 paper of Hartmanis and Stearns^[1] and the 1972 book by Garey and Johnson on NP-completeness, ^[2] the term "computational complexity" (of algorithms) most commonly refers to the 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 Oh", e.g.. O(n²). 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.

In most practical cases deterministic algorithms or randomized algorithms are discussed, although theoretical computer science also considers nondeterministic algorithms and other advanced models of computation.

[edit] References