Complexity

From Glossary

Jump to: navigation, search

A measure of computer time or space to solve a problem by an algorithm as a function of the problem's dimensions. Suppose LaTeX: T(n) is the time it takes to solve an instance of the problem with dimension LaTeX: n. Then, the algorithm has (worst-case) time complexity LaTeX: K(n), if the greatest time it could take to solve an instance of the problem is LaTeX: O(K(n)). When LaTeX: K(n) is a polynomial, we say the algorithm has polynomial time complexity. The Klee-Minty polytope shows that the elementary simplex method does not have polynomial time complexity.

The average time complexity is the average (rather than worst) time of an algorithm (or class of algorithms) over some class of problems, for which some probability distribution is assumed. Absent a modifier, the complexity of an algorithm is taken to mean its worst-case time complexity.

Whereas complexity refers to the performance of an algorithm, see the notion of NP-completeness for the related meaning of problem complexity. The standard notation to describe complexity in terms of problem dimensions, say LaTeX: n, is LaTeX: O(K(n)). This ``big-O notation means the following: a function, LaTeX: f:Z^+ \rightarrow R, is LaTeX: O(K(n)) if there exists a constant, LaTeX: c, and LaTeX: N in LaTeX: Z^+, such that LaTeX: f(n) \le cK(n) for all LaTeX: n \ge N. For example, if an algorithm requires LaTeX: 5n^3 + 2n + 10 fundamental operations on a problem of size LaTeX: n, its time complexity is LaTeX: O(n^3). See the supplement on complexity for more information.


Views
Personal tools