## Institute for Mathematical Sciences

## Preprint ims09-01

** Myong-Hi Kim, Marco Martens, and Scott Sutherland**
*A Universal Bound for the Average Cost of Root Finding*

Abstract: We analyze a path-lifting algorithm for finding an approximate zero of acomplex polynomial, and show that for any polynomial with distinct roots in the
unit disk, the average number of iterates this algorithm requires is
universally bounded by a constant times the log of the condition number. In
particular, this bound is independent of the degree $d$ of the polynomial. The
average is taken over initial values $z$ with $|z| = 1 + 1/d$ using uniform
measure.

View ims09-01 (PDF format)