1998 Reports

# What Is the Complexity of Stieltjes Integration?

We study the complexity of approximating the Stieltjes integral ∫ 0^1 f(x)dg(x) for functions ƒ having r continuous derivatives and functions g whose sth derivative has bounded variation. Let r(n) denote the nth minimal error attainable by approximations using at most~n evaluations of ƒ 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 algorithm that computes an ε-approximation at nearly-minimal cost.

## Subjects

## Files

- cucs-017-98.pdf application/pdf 62.8 KB Download File

## More About This Work

- Academic Units
- Computer Science
- Publisher
- Department of Computer Science, Columbia University
- Series
- Columbia University Computer Science Technical Reports, CUCS-017-98
- Published Here
- April 25, 2011