\left[ 
\left( m \frac{\gamma}{\delta} \right)^{\log
\left( 1 - \frac{\delta}{m\gamma} \right)}
\right]^{m \frac{\gamma}{\delta}}
\nonumber \\
& \le & m \gamma \left[ \left( 
m \frac{\gamma}{\delta} \right)^{- \frac{\delta}{m\gamma}} 
\right]^{m \frac{\gamma}{\delta}} \le \delta.
\label{myIneq6}\end{aligned}$$ Therefore, after at most $\lceil t \rceil$ iterations, $x_{\bar{j}}^{k+t}< \delta$ holds. In view of Assumption 4, we conclude that $x_{\bar{j}}^{k+t}$ is not a basic variable of $B^{k+t}$ and (\[myIneq2\]) asserts that it will not be a basic variable thereafter. [&lt;1.5em -1.5em plus0em minus0.5em height0.75em width0.5em depth0.25em]{}

The scenario described in the theorem can occur at most one time for each optimal non-basic variable and since there are $n-m$ non-basic optimal variables, we have the following theorem.

For the double-pivot algorithm \[mainAlg\], it needs at most $(n-m) \Bigl\lceil
m \frac{\gamma}{\delta}
\log\left( m \frac{\gamma}{\delta} \right)
\Bigr\rceil$ iterations to find the optimal solution of (\[LP\]).

The way of selecting $x_{\bar{j}}^{k}$ below (\[myIneq2\]) implies that one should consider the entering variable that takes the longest step because this variable is likely an optimal non-basic variable. \[longestStep\]

Similar to the argument in [@km13a], we can apply the above theorem to some special linear programming problems, such as LP with a totally unimodular matrix and Markov Decision Problem with a fixed discount rate, and show that 