 # Complexity

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