Find an algorithm to evaluate unknown polynomial of degree $n$ given its values for $x=0,x=1, x=2,\ldots,x=n$ Given $n+1$ values ($P(0),P(1), P(2),\ldots,P(n)$) of unknown polynomial $P(x)$ of degree $n$ find an algorithm that works in $O(n^2)$ for evaluating $P(n+1), P(n+2),\ldots,P(2n)$.
Given $n+1$ values you could find polynomial coefficients explicitly but it'll take $O(n^3)$.
 A: You can use finite differences to find the other values: Just write these values in one line, the differences between consecutive values in the next line, the differences between consecutive differences in the next line, and so on for $n$ lines. The last line has only one value but it is actually constant. Now work your way up to find the values of $P$ at the other points.
Here is an example for $P(x)=x^3+1$:
$$
\begin{array}{llll}
1 & 2 & 9 & 28\\
1 & 7 & 19\\
6 & 12\\
6
\end{array}
\qquad\to\qquad 
\begin{array}{llll}
1 & 2 & 9 & 28 & 65 & 126 & 217\\
1 & 7 & 19 & 37 & 61 & 91\\
6 & 12 & 18 & 24 & 30\\
6 & 6 & 6 & 6
\end{array}
$$
The data on the left consists of $O(n^2)$ values computed top-down at cost $O(1)$ per entry. The new data on the right consists of $O(n^2)$ values computed bottom-up at cost $O(1)$ per entry. Hence the total cost is $O(n^2)$.
This technique also works for finding a polynomial of degree $n$ from its values at $n+1$ consecutive integers. See Newton's series. The polynomial will be expressed in the binomial basis, not the power basis, using the coefficients in the first column.
