Given a univariate polynomial f (z) of degree n with complex coefficients, whose norms are less than 2 m in magnitude, the root problem is to find all the roots of f (z) up to specified precision 2 ฯชศ . Assuming the arithmetic model for computation, we provide an algorithm which has complexity O(n log 5 n log B), where b ฯญ ฯฉ ศ, and ฯญ maxอn, mอ. This improves on the previous best known algorithm of Pan for the problem, which has complexity O(n 2 log 2 n log(m ฯฉ ศ)). A remarkable property of our algorithm is that it does not require any assumptions about the root separation of f, which were either explicitly, or implicitly, required by previous algorithms. Moreover it also has a work-efficient parallel implementation. We also show that both the sequential and parallel implementations of the algorithm work without modification in the Boolean model of arithmetic. In this case, it follows from root perturbation estimates that we need only specify ฯญ ๏ฃฎn(B ฯฉ log n ฯฉ 3)๏ฃน bits of the binary representations of the real and imaginary parts of each of the coefficients of f. We also show that by appropriate rounding of intermediate values, we can bound the number of bits required to represent all complex numbers occurring as intermediate quantities in the computation. The result is that we can restrict the numbers we use in every basic arithmetic operation to those having real and imaginary parts with at most bits, where ฯญ ศ ฯฉ 2n 2 ฯฉ 3(n ฯฉ log n ฯฉ 1) ฯฉ n 2 (1 ฯฉ 2 log n) ฯฉ log log n