Topological complexity of a root finding algorithm (Q582007)

Defining the set of the polynomials by \(P_ d(1)=\{f(z)=\sum^{d}_{j=0}a_ jz^ j,\quad a_ d=1,\quad | a_ j| \leq 1\},\) the author proposes an algorithm for solving the following problem: For any \(f\in P_ d(1)\), any \(\epsilon >0\), find \(\{x_ j\}\) j-1,...,d, such that \(| x_ j-\xi_ j| \leq \epsilon\), where \(f(z)=\prod^{d}_{j-1}(z-\xi_ j).\) The paper is focused on minimizing the branching nodes (or topological complexity) appearing in the algorithm. It is shown that the topological complexity of the proposed algorithm is (d-1) and the depth of this algorithm is (log d). For a subclass of \(P_ d(1)\) of real polynomials with only real roots an algorithm is given which always finds all d \(\epsilon\)-roots, i.e. the topological complexity is 0.