On the Average Case Errors of Numerical Integration Rules using Interpolation

Among many algorithms for the integration problems in which one wants to compute the approximation to the definite integral in the average case setting, we study the average case errors of numerical integration rules using interpolation. In particular, we choose the composite Newton-Cotes quadratures and the function values at equally spaced sample points on the given interval as information. We compute the average case error of composite Newton-Cotes quadratures and show that it is minimal(modulo a multiplicative constant).