to show that the following upper bound of iteration numbers of Algorithm \[mainAlg\] holds.

Suppose that we generate a sequence of basic feasible solutions by Algorithm \[mainAlg\] from an initial iterate $\x^0$. Then, the number of total iterations is bounded above by $$\Bigl\lceil 
\frac{\c^{\Tr} \x^0 - z^*}{\delta_D \gamma_{\ell}}
\Bigr\rceil \le
\Bigl\lceil
\frac{\gamma_D^0\| \x^* \|_1 }
{\delta_D \gamma_{\ell}}
\Bigr\rceil
\label{bound}$$ \[mainThe\]

The bound of the left side is obvious. By the defintion of $\gamma_D^k$, we have $$\bar{\c}_{N^k}^{\Tr}\x_{N^k}^* \ge 
-{\gamma_D^k \| \x_{N^k}^* \|_1 }.$$ Therefore, for initial step, the last inequality of (\[est1\]) can be replaced by $$\c^{\Tr} \x^0 - z^* \le \gamma_D^0 \| \x^* \|_1 .$$ Since every iteration will reduce the objective function at least a constant $\delta_D \gamma_{\ell}$, we need at most $$\Bigl\lceil
\frac{\gamma_D^0 \| \x^* \|_1 }
{\delta_D \gamma_{\ell}}
\Bigr\rceil$$ iterations to find the optimal solution. [&lt;1.5em -1.5em plus0em minus0.5em height0.75em width0.5em depth0.25em]{}

The upper bound given in Theorem \[mainThe\] is smaller than the one in [@km13] because (a) $\gamma_{\ell}$ is the smallest value in all longest steps among all iterates while the corresponding number in [@km13] is the smallest value in all nonzero components among all iterates $\x^k$, (b) $\| \x^* \|_1 $ depends only on the 