# Klee-Minty polytope

### From Glossary

This is an example to show that the elementary simplex method
does not have polynomial time complexity. The polytope is

Maximizing

over this polytope shows the exponential complexity.

Complexity |

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.