Complexity of recovering all roots of a polynomial

Given a polynomial of degree n and a list of putative roots $$\{r_i\}_{i=1}^{n}$$, we can verify that all the putative roots are indeed correct by $$n$$ applications of Horner's method. Hence verifying the solution requires $$\mathcal{O}(n)$$ storage and $$\mathcal{O}(n^2)$$ floating point operations.

Now, if we use the method described here we find that we compute all roots of a polynomial using $$\mathcal{O}(n)$$ storage and $$\mathcal{O}(n^2)$$ flops in a backwards-stable way.

Since computing the roots and verifying they are correct have the same complexity, it feels like $$\mathcal{O}(n)$$ storage and $$\mathcal{O}(n^2)$$ flops is optimal. (Certainly the storage is optimal complexity.)

Could there exist a faster method to recover the roots than $$\mathcal{O}(n^2)$$? Have $$\mathcal{O}(n\log n)$$ algorithms been ruled out somehow?

• Since you can't get analytic values (within the subset of real numbers which includes "pure" roots), the computational methods will also depend on the allowable error. Is it shown that, for computed roots of error $\epsilon$ you can do the polynomial evaluation to the same $\epsilon$ or a matching $\delta$ (to steal from Calculus) in the same order of time? Commented Mar 10, 2022 at 15:02
• @CarlWitthoft: I believe that you cannot guarantee any error on the root, only the backward error. Commented Mar 10, 2022 at 16:25

Evaluating a polynomial of degree $$ in $$n$$ points can be done in time $$O(n\log n)$$. This is called fast multipoint evaluation; see for instance von zur Gathen, Modern Computer Algebra, ch. 10.
• @CarlWitthoft Yes, this is more a frame challenge than an answer. OP starts from the assumption that verifying that $n$ points are roots (evaluating) costs $O(n^2)$. But (surprisingly and non-obviously) this assumption is wrong, as there is a better algorithm in literature. Commented Mar 10, 2022 at 15:23