# Complexity of polynomial interpolation

Polynomial Interpolation in the general case is $O(n^2)$ time complexity, but it can be done better in particular situations. For instance, when the polynomial can be evaluated at the complex roots of unity, it can be interpolated in $O(n\log n)$ time with the Fast Fourier Transform. Or at least, that's the only situation that I am aware of that can be done better than $O(n^2)$.

Are there any other forms of input that can be interpolated in better than $O(n^2)$ time?

I am particularly interested in knowing whether or not there is an algorithm that interpolates a polynomial from evenly spaced points (in the x-coordinate that is) that beats $O(n^2)$, because I think I've come up with something that does it in $O(n\log n)$ time.

• It’s often irrelevant because interpolation with large n becomes numerically unstable. You really don’t want to put a degree 100 polynomial through 101 points. Jul 6, 2018 at 10:06
• And evenly spaced isn’t very good. Look up Chebychev or Clenshaw/Curtis (not sure about the names and spelling) Jul 6, 2018 at 10:08
• @gnasher729 It's perfectly good f.e. in Galois Fields. In particular I used it for fast Reed-Solomon codec: github.com/Bulat-Ziganshin/FastECC - we evaluate order-N polynomial at M points at encoding and then can restore polynomial coefficients from any N survived points. Jul 6, 2018 at 10:52

Fast polynomial interpolation and Fast polynomial evaluation are algorithms that seem to be discovered back in 1973. They allow to interpolate/evaluate polynomial at N arbitrary points as far as field has 2N (?) roots of unity. Both are based on Fast polynomial division. All three are $O(n\log^2 n)$ time.
• So, to clarify, there are already algorithms that can interpolate a polynomial from any arbitrary set of points in $O(n\log^2 n)$, and polynomial interpolation is not in fact $O(n^2)$ in the general case? Jul 6, 2018 at 20:47
• Is it known if we can do better in case of finite fields with prime order $p$ and at interpolation points $1, 2, 3, ..., n$? Jun 21 at 9:19