We study the complexity of approximating stochastic integrals with error ep
silon for various classes of functions. For Ito integration, we show that t
he complexity is of order epsilon (-1), even for classes of very smooth fun
ctions. The lower bound is obtained by showing that Ito integration is not
easier than Lebesgue integration in the average case setting with the Wiene
r measure. The upper bound is obtained by the Milstein algorithm, which is
almost optimal in the considered classes of functions. The Milstein algorit
hm uses the values of the Brownian motion and the integrand. It is bilinear
in these values and is very easy to implement. For Stratonovich integratio
n, we show that the complexity depends on the smoothness of the integrand a
nd may be much smaller than the complexity of Ito integration.