It is an open question whether there is an interior-point algorithm for linear optimization problems with a lower iteration-complexity than the classical bound $\mathcal{O}(\sqrt{n} \log(\frac{\mu_1}{\mu_0}))$. This paper provides a negative answer to that question for a variant of the Mizuno-Todd-Ye predictor-corrector algorithm. In fact, we prove that for any $\epsilon >0$, there is a redundant Klee-Minty cube for which the aforementioned algorithm requires $n^{( \frac{1}{2}-\epsilon )} $ iterations to reduce the barrier parameter by at least a constant. This is provably the first case of an adaptive step interior-point algorithm, where the classical iteration-complexity upper bound is shown to be tight.