Counterexamples in Optimal Quadrature

It is widely believed that order of exactness is a good measure of the quality of an algorithm for numerical quadrature. We show that this is not the case, by exhibiting a situation in which the optimal algorithm does not even integrate constants exactly. We also show that there are situations in which the penalty for using equidistant nodes is unbounded. Finally, we show that the complexity of obtaining an ε-approximation can be an arbitrary function of ε, i.e., there is no hardest quadrature problem