# Complexity

### From Glossary

A measure of computer time or space to
solve a problem by an algorithm as a function of
the problem's dimensions. Suppose is the time it takes to
solve an instance of the problem with dimension . Then, the
algorithm has (worst-case) time complexity , if the greatest
time it could take to solve an instance of the problem is .
When 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 , is
. This ``big-O* notation means the following: a function,*
, is if there exists
a constant, , and in , such that
for all . For example, if an
algorithm requires fundamental operations on a problem
of size , its time complexity is . See the
supplement on complexity
for more information.