What is the time complexity in solving a polynomial equation of degree N in one variable?
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 &lt;0, and you need to know this to know the number of roots near to x (0, 1, or 2).