What is the complexity of Stieltjes integration?

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.