Let $f$ be a univariate polynomial with real coefficients, $f\in\RR[X]$. Subdivision algorithms based on algebraic techniques (e.g., Sturm or Descartes methods) are widely used for isolating the roots of $f$ in a given interval. In this paper, we consider subdivision algorithms based on purely numerical primitives such as function evaluation.
Such methods have adaptive complexity, are local, and are also applicable when $f$ is transcendental. The complexity analysis of adaptive algorithms is a new challenge for computer science. In this paper, we introduce a form of continuous amortization for adaptive complexity.

Our analysis is applied to an evaluation-based root isolation algorithm called EVAL. EVAL is based on an algorithm of Mitchell and can also be seen as a 1-dimensional analogue of algorithms by Plantinga and Vegter for meshing curves and surfaces. The algorithm itself is simple, but its complexity analysis is not. Our main result is an $O(d^3(\log d+L))$ bound on the subdivision-tree size of EVAL for the benchmark problem of isolating all real roots of a
square-free integer polynomial $f$ of degree $d$ and logarithmic height $L$.

Our proof introduces several novel techniques: First, we provide an adaptive upper bound on the complexity of EVAL using an integral, analogous to integral bounds provided by Ruppert in a different context. Such integrals can be viewed as a form
of continuous amortization. In addition, we
use two algebraic amortization techniques: one is
based on the standard Mahler-Davenport root bounds, but the other, based on evaluation bounds, is new.