We study the complexity of approximating the Stieltjes integral integral(0)
(1)f(x) dg(x) for functions f having r continuous derivatives and functions
g whose sth derivative has bounded variation. Let r(n) denote the nth mini
mal error attainable by approximations using at most n evaluations of f and
g, and let comp(epsilon) denote the epsilon-complexity (the minimal cost o
f computing an epsilon-approximation). We show that r(n)asymptotic to=n(-mi
n{r, s+1}) and that comp(epsilon)asymptotic to epsilon(-1/min{r, s+1}). We
also present an algorithm that computes an epsilon-approximation at nearly
minimal cost. (C) 2000 Academic Press.