On the worst-case arithmetic complexity of approximating zeros of polynomials
James Renegar · Journal of Complexity · 1987
Let Pd(R) denote the set of degree d complex polynomials with all zeros ζ satisfying |ζ| ≤ R. For d ≥ 2 fixed, we show that with respect to a certain model of computation, the worst-case computational complexity of obtaining an ε-approximation either to one, or to each, zero of arbitrary f ∈ Pd(R) is Θ(log log(R/ε)), that is, we prove both upper and lower bounds. A new algorithm, based on Newton's method, is introduced for proving the upper bound.