  Approximating the roots of a holomorphic function in an input box is a
fundamental problem in many domains. Most algorithms in the literature for
solving this problem are conditional, i.e., they make some simplifying
assumptions, such as, all the roots are simple or there are no roots on the
boundary of the input box, or the underlying machine model is Real RAM. Root
clustering is a generalization of the root approximation problem that allows
for errors in the computation and makes no assumption on the multiplicity of
the roots. An unconditional algorithm for computing a root clustering of a
holomorphic function was given by Yap, Sagraloff and Sharma in 2013. They
proposed a subdivision based algorithm using effective predicates based on
Pellet's test while avoiding any comparison with zeros (using soft zero
comparisons instead). In this paper, we analyze the running time of their
algorithm. We use the continuous amortization framework to derive an upper
bound on the size of the subdivision tree. We specialize this bound to the case
of polynomials and some simple transcendental functions such as exponential and
trigonometric sine. We show that the algorithm takes exponential time even for
these simple functions, unlike the case of polynomials. We also derive a bound
on the bit-precision used by the algorithm. To the best of our knowledge, this
is the first such result for holomorphic functions. We introduce new geometric
parameters, such as the relative growth of the function on the input box, for
analyzing the algorithm. Thus, our estimates naturally generalize the known
results, i.e., for the case of polynomials.
