What Is the Complexity of Stieltjes Integration?

We study the complexity of approximating the Stieltjes integral 1 0 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 minimal error attainable by appro- ximations using at most n evaluations of f and g, and let comp(=) denote the =-complexity (the minimal cost of computing an =-approximation). We show that r(n) n&min[r, s+1] and that comp(=) =&1 min[r, s+1]. We also present an algo- rithm that computes an =-approximation at nearly minimal cost.