How easy/difficult(in terms of big-O) is it to solve polynomial equations of high degrees of N?

Do apps like Desmos actually solve equations to get roots or do they approximate roots by iterating through a range of values for x?

What mechanisms are at play in solving a univariate polynomial equation algorithmically?

  • 2
    $\begingroup$ What do you mean by solving? How is the solution represented? $\endgroup$ – Yuval Filmus Dec 1 '19 at 12:07
  • $\begingroup$ By "solving" I mean obtaining a list of all its real roots $\endgroup$ – Akshay Vasudeva Rao Dec 1 '19 at 12:33
  • 1
    $\begingroup$ How are the solutions represented? Even assuming that the coefficients are integers, the solutions need not be rational. Perhaps you want, given some $\epsilon > 0$, a list of all roots up to error $\epsilon$? $\endgroup$ – Yuval Filmus Dec 1 '19 at 12:59
  • $\begingroup$ en.wikipedia.org/wiki/…, en.wikipedia.org/wiki/Factorization_of_polynomials $\endgroup$ – D.W. Dec 1 '19 at 18:18
  • $\begingroup$ @D.W. Thanks! That helped :) $\endgroup$ – Akshay Vasudeva Rao Dec 2 '19 at 6:34

The time complexity doesn't just depend on N. It's possible that due to the coefficients, you have to evaluate the polynomial with very high precision to determine whether some minimum of the polynomial near a point x has a value >0, =0 or <0, and you need to know this to know the number of roots near to x (0, 1, or 2).

| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.