  By the seminal paper of Claude Shannon \cite{Shannon48}, the computation of
the capacity of a discrete memoryless channel has been considered as one of the
most important and fundamental problems in Information Theory. Nearly 50 years
ago, Arimoto and Blahut independently proposed identical algorithms to solve
this problem in their seminal papers \cite{Arimoto1972AnAF,
Blahut1972ComputationOC}. The Arimoto-Blahut algorithm was proven to converge
to the capacity of the channel as $t \to \infty$ with the convergence rate
upper bounded by $O\left(\log(m)/t\right)$, where $m$ is the size of the input
distribution, and being inverse exponential when there is a unique solution in
the interior of the input probability simplex \cite{Arimoto1972AnAF}. Recently
it was proved, in \cite{Nakagawa2020AnalysisOT}, that the convergence rate is
at worst inverse linear $O(1/t)$ in some specific cases.
  In this paper, we revisit this fundamental algorithm looking at the rate of
convergence to the capacity and the time complexity, given $m,n$, where $n$ is
size of the output of the channel, focusing on the approximation of the
capacity. We prove that the rate of convergence to an $\varepsilon$-optimal
solution, for any constant $\varepsilon > 0$, is inverse exponential
$O\left(\log(m)/c^t\right)$, for a constant $c > 1$ and $O\left(\log \left(\log
(m)/\varepsilon\right)\right)$ at most iterations, implying $O\left(m n\log
\left(\log (m)/\varepsilon\right)\right)$ total complexity of the algorithm.
