On the Complexity of Zero Finding for Univariate Functions

We study the zero finding problem for univariate functions changing sign at the endpoints of an interval, and we survey some results of different authors. The complexity of zero finding, i.e., the minimal cost to determine a zero with a given accuracy ¿, is studied in the worst and in the average case setting. For classes of smooth functions the results in both settings differ significantly. While ln(1/¿) is the order of the worst case complexity, the average case complexity is at most of the order ln ln(1/¿).