3
$\begingroup$

The Wikipedia article on finding the roots of polynomials mentions all sorts of methods to do so. But it doesn't give, nor can one easily figure out by following the links, known lower and upper bounds on time complexity in various models (and which approaches achieve them).

So, if we're given the $n$ real coefficients of a degree $n-1$ univariate polynomial - each of them as a floating point value with $m$ mantissa digits and $p$ exponent digits - what's the time complexity for a random-access machine to compute all of its real + imaginary roots to within $\delta$ of their actual values? How much for just the real roots?

Note:

  • this goes some of the way to relate coefficient complexity measures to search space size.
  • If you'd rather answer for a slightly different formalization of the problem, that's fine too.
  • The "best bound I know personally is XYZ" is also a useful answer.
  • Do not assume the roots are distinct or all real.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.