  Using the interplay between topological, combinatorial, and geometric
properties of polynomials and analytic results (primarily the covering
structure and distortion estimates), we analyze a path-lifting method for
finding approximate zeros, similar to those studied by Smale, Shub, Kim, and
others. Given any polynomial, this simple algorithm always converges to a root,
except on a finite set of initial points lying on a circle of a given radius.
  Specifically, the algorithm we analyze consists of iterating $$z -
\frac{f(z)-t_kf(z_0)}{f'(z)}$$ where the $t_k$ form a decreasing sequence of
real numbers and $z_0$ is chosen on a circle containing all the roots. We show
that the number of iterates required to locate an approximate zero of a
polynomial $f$ depends only on $\log|f(z_0)/\rho_\zeta|$ (where $\rho_\zeta$ is
the radius of convergence of the branch of $f^{-1}$ taking $0$ to a root
$\zeta$) and the logarithm of the angle between $f(z_0)$ and certain critical
values. Previous complexity results for related algorithms depend linearly on
the reciprocals of these angles. Note that the complexity of the algorithm does
not depend directly on the degree of $f$, but only on the geometry of the
critical values.
  Furthermore, for any polynomial $f$ with distinct roots, the average number
of steps required over all starting points taken on a circle containing all the
roots is bounded by a constant times the average of $\log(1/\rho_\zeta)$. The
average of $\log(1/\rho_\zeta)$ over all polynomials $f$ with $d$ roots in the
unit disk is ${\mathcal{O}}({d})$. This algorithm readily generalizes to
finding all roots of a polynomial (without deflation); doing so increases the
complexity by a factor of at most $d$.
