Asymptotic behaviour of automatic quadrature

The complexity of automatic quadrature programs is investigated under the hypothesis of exactness or asymptotical consistence of local error estimates. The complexity measure used is the number N of functional evaluations in real exact arithmetic versus the number E of exact decimal digits in the result. The methods of integration analysed are m-panel rules, Clenshaw-Curtis quadrature, Romberg method, global adaptive quadrature, and double adaptive quadrature. For m-panel and global adaptive quadrature, based on a local rule of degree r-1 the constants hidden by the "Oh" notation are determined in terms of the r-th derivative of the integrand and the numerical properties of the chosen local rule. The complexity of global adaptive quadrature results to be of order ?(10?E/r), regardless of the regularity of the integrand. The double adaptive quadrature achieves O(E) complexity for regular integrands and O(E?2) for singular ones.