Polynomial interpolation

Problem Description

Polynomial interpolation is a method of estimating values between known data points. When graphical data contains a gap, but data is available on either side of the gap or at a few specific points within the gap, an estimate of values within the gap can be made by interpolation.

The simplest method of interpolation is to draw straight lines between the known data points and consider the function as the combination of those straight lines. This method, called linear interpolation, usually introduces considerable error. A more precise approach uses a polynomial function to connect the points. A polynomial is a mathematical expression comprising a sum of terms, each term including a variable or variables raised to a power and multiplied by a coefficient. The simplest polynomials have one variable. Polynomials can exist in factored form or written out in full.

Bounds Chart

Step Chart

Improvement Table

Complexity Classes	Algorithm Paper Links	Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3
Cubic	[ Gaussian elimination (-150)]
Quadratic	[ Bjorck (1970)] [ Higham (1988)] [ Calvetti, Reichel (1993)]
nlogn
Linear
logn