  We connect known results about diffusion limits of Markov chain Monte Carlo
(MCMC) algorithms to the Computer Science notion of algorithm complexity. Our
main result states that any diffusion limit of a Markov process implies a
corresponding complexity bound (in an appropriate metric). We then combine this
result with previously-known MCMC diffusion limit results to prove that under
appropriate assumptions, the Random-Walk Metropolis (RWM) algorithm in $d$
dimensions takes $O(d)$ iterations to converge to stationarity, while the
Metropolis-Adjusted Langevin Algorithm (MALA) takes $O(d^{1/3})$ iterations to
converge to stationarity.

Probability