# Klee-Minty polytope

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

$LaTeX: \left\{ x : \left(\sum_{i=1}^{k-1} 2^{k-i+1} x_i \right) + x_k \le 5^k,

 \; \mbox{ for } k = 1, 2, \ldots, n, \; x \ge 0 \right\}

$

Maximizing

$LaTeX: \sum_{i=1}^n 2^{n-i} x_i$

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