Computational complexity on numerical integrals (Q1177970)

This paper analyzes the computational complexity of one-dimensional integration formulas. The authors generalize some earlier work by Smale in this area. Their main result is an explicit formula for the expected error from a degree \(k-1\) quadrature formula, with the average taken over functions in an appropriate Sobolev space. Exact error constants for the midpoint, trapezoidal and Simpson formulas are given.