<p>It could be that the variants refer to two different forms of Linear Programs. Simplex only works with problems in Standard Equality Form (SEF) which is of the form <span class="math-container">$$\min c^T x\,\,\,\,\text{s.t.}\,\,\,\, Ax=b,\, x \geq 0$$</span> Linear algebra tells us that this only has a solution if the rank of the matrix <span class="math-container">$A$</span> is at least the dimension of <span class="math-container">$b$</span>, which for us is <span class="math-container">$m$</span>. But <span class="math-container">$\texttt{rank}(A) \leq \min\{n,m\}$</span> so in order to have a solution at all, we need <span class="math-container">$n \geq m$</span>.</p>
<p>The number of pivots that occur during the Simplex algorithm (assuming you implement a pivoting rule that prohibits cycling) is at most the number of different bases you can make with the columns of <span class="math-container">$A$</span>, which is <span class="math-container">$\binom{n}{m} &lt; 2^n$</span> (since <span class="math-container">$m \leq n$</span>).  Thus the number of pivots is <span class="math-container">$O(2^n)$</span>.</p>
<p>However, if you want to solve a Linear Program that is not in SEF then you need to first put it into SEF. When you do this any &quot;free&quot; variable (one not constrained to be nonnegative or nonpositive) is split into two and we introduce &quot;slack variables for each inequality constraint. If we let <span class="math-container">$n'$</span> be the number of variables in this new version of the problem, then we have <span class="math-container">$n' \leq 2n + m$</span> and thus the number of pivots is <span class="math-container">$O(2^{2n+m})$</span>. [If the original problem had nonnegative variables, but all inequality constraints, then <span class="math-container">$n' = n + m$</span> which is probably the case in the second variant you found.]</p>
<p>However, both of these don't factor in the running time of each pivot. I have never seen a careful analysis of the running time of each pivot, and it will depend on implementation, but I think a straightforward implementation and analysis would achieve a runtime of <span class="math-container">$O(n+m^\omega)$</span>, where <span class="math-container">$\omega$</span> is the number such that you can invert an <span class="math-container">$m \times m$</span> matrix in <span class="math-container">$O(m^\omega)$</span> running time. Thus I would say that the running time for solving an arbitrary linear program with the simplex method is <span class="math-container">$O\left((n+m^\omega)2^{2n+m}\right)$</span> but I am not confident about the <span class="math-container">$(n+m^\omega)$</span> factor.</p>

CC BY-SA 4.0
2023-12-13T21:22:27.143Z
2023-12-13T21:22:27.143Z
NaturalLogZ
<p>What is the complexity of the simplex method in terms of Big O in the general case? I saw two variants: O(2^n) and O(2^(n+m)), where n is the number of variables and m is the number of constraints</p>

<cc.complexity-theory><ds.algorithms><linear-programming><simplex>
Complexity of simplex method
Kitty
# Complexity of simplex method

(Asked by: username_0 on 2023-12-13)

What is the complexity of the simplex method in terms of Big O in the general case? I saw two variants: O(2^n) and O(2^(n+m)), where n is the number of variables and m is the number of constraints

**Tags:** cc.complexity-theory, ds.algorithms, linear-programming, simplex


---

## 1 answers

### Answer by username_1 on 2023-12-13. Score: 4

It could be that the variants refer to two different forms of Linear Programs. Simplex only works with problems in Standard Equality Form (SEF) which is of the form $$\min c^T x\,\,\,\,\text{s.t.}\,\,\,\, Ax=b,\, x \geq 0$$ Linear algebra tells us that this only has a solution if the rank of the matrix $A$ is at least the dimension of $b$, which for us is $m$. But $\texttt{rank}(A) \leq \min\{n,m\}$ so in order to have a solution at all, we need $n \geq m$.

The number of pivots that occur during the Simplex algorithm (assuming you implement a pivoting rule that prohibits cycling) is at most the number of different bases you can make with the columns of $A$, which is $\binom{n}{m} < 2^n$ (since $m \leq n$). Thus the number of pivots is $O(2^n)$.

However, if you want to solve a Linear Program that is not in SEF then you need to first put it into SEF. When you do this any "free" variable (one not constrained to be nonnegative or nonpositive) is split into two and we introduce "slack variables for each inequality constraint. If we let $n'$ be the number of variables in this new version of the problem, then we have $n' \leq 2n + m$ and thus the number of pivots is $O(2^{2n+m})$. [If the original problem had nonnegative variables, but all inequality constraints, then $n' = n + m$ which is probably the case in the second variant you found.]

However, both of these don't factor in the running time of each pivot. I have never seen a careful analysis of the running time of each pivot, and it will depend on implementation, but I think a straightforward implementation and analysis would achieve a runtime of $O(n+m^\omega)$, where $\omega$ is the number such that you can invert an $m \times m$ matrix in $O(m^\omega)$ running time. Thus I would say that the running time for solving an arbitrary linear program with the simplex method is $O\left((n+m^\omega)2^{2n+m}\right)$ but I am not confident about the $(n+m^\omega)$ factor.


---

