Recall from our basics discussion that a polynomial $\phi$ of degree $d$ is a vector of $d+1$ coefficients:
\begin{align} \phi &= [\phi_0, \phi_1, \phi_2, \dots, \phi_d] \end{align}
How to compute a polynomial’s coefficients from a bunch of its evaluations
Given $n$ pairs $(x_i, y_i)_{i\in[n]}$, one can compute or interpolate a degree $\le n1$ polynomial $\phi(X)$ such that: \(\phi(x_i)=y_i,\forall i\in[n]\)
Specifically, the Lagrange interpolation formula says that: \begin{align} \label{eq:lagrangeformula} \phi(X) &= \sum_{i\in[n]} y_i \cdot \lagr_i(X),\ \text{where}\ \lagr_i(X) = \prod_{j\in[n],j\ne i} \frac{Xx_j}{x_ix_j} \end{align}
This formula is intimidating at first, but there’s a very simple intuition behind it. The key idea is that $\lagr_i(X)$ is defined so that it has two properties:
 $\lagr_i(x_i) = 1,\forall i\in[n]$
 $\lagr_i(x_j) = 0,\forall j \in [n]\setminus\{i\}$
You can actually convince yourself that $\lagr_i(X)$ has these properties by plugging in $x_i$ and $x_j$ to see what happens.
Important: The $\lagr_i(X)$ polynomials are dependent on the set of $x_i$’s only (and thus on $n$)! Specifically each $\lagr_i(X)$ has degree $n1$ and has a root at each $x_j$ when $j\ne i$! In this sense, a better notation for them would be $\lagr_i^{[x_i, n]}(X)$ or $\lagr_i^{[n]}(X)$ to indicate this dependence.
Example: Interpolating a polynomial from three evaluations
Consider the following example with $n=3$ pairs of points. Then, by the Lagrange formula, we have:
\[\phi(X) = y_1 \lagr_1(X) + y_2 \lagr_2(X) + y_3 \lagr_3(X)\]Next, by applying the two key properties of $\lagr_i(X)$ from above, you can easily check that $\phi(x_i) = y_i,\forall i\in[3]$:
\begin{align}
\phi(x_1) &= y_1 \lagr_1(x_1) + y_2 \lagr_2(x_1) + y_3 \lagr_3(x_1) = y_1 \cdot 1 + y_2 \cdot 0 + y_3 \cdot 0 = y_1\\
\phi(x_2) &= y_1 \lagr_1(x_2) + y_2 \lagr_2(x_2) + y_3 \lagr_3(x_2) = y_1 \cdot 0 + y_2 \cdot 1 + y_3 \cdot 0 = y_2\\
\phi(x_3) &= y_1 \lagr_1(x_3) + y_2 \lagr_2(x_3) + y_3 \lagr_3(x_3) = y_1 \cdot 0 + y_2 \cdot 0 + y_3 \cdot 1 = y_3
\end{align}
An important detail is that the degree of the interpolated $\phi(X)$ is $\le n1$ and not necessarily exactly equal to $n1$. To see this, consider interpolating the polynomial $\phi(X)$ such that $\phi(i) = i$ for all $i\in [n]$. In other words, $x_i = y_i = i$.
The inspired reader might notice that the polynomial $\phi(X) = X$ could satisfy our constraints.
But is this what the Lagrange interpolation will return?
After all, the interpolated $\phi(X)$ is a sum of degree $n1$ polynomials $\lagr_i(X)$, so could it have degree 1?
Well, it turns out, yes, because things cancel out.
To see this, take a simple example, with $n=3$:
\begin{align}
\phi(X) &=\sum_{i\in [3]} i \cdot \lagr_i(X) = \sum_{i\in [3]} i \cdot \prod_{j\in[3]\setminus{i}} \frac{X  j}{i  j}\\
&= 1\cdot \frac{X2}{12}\frac{X3}{13} + 2\cdot \frac{X1}{21}\frac{X3}{23} + 3\cdot\frac{X1}{31}\frac{X2}{32}\\
&= \frac{X2}{1}\frac{X3}{2} + 2\cdot \frac{X1}{1}\frac{X3}{1} + 3\cdot \frac{X1}{2}\frac{X2}{1}\\
&= \frac{1}{2}(X2)(X3)  2(X1)(X3) + \frac{3}{2}(X1)(X2)\\
&= \frac{1}{2}[(X2)(X3) + 3(X1)(X2)]  2(X1)(X3)\\
&= \frac{1}{2}[(X2)(4X6)]  2(X1)(X3)\\
&= (X2)(2X3)  2(X1)(X3)\\
&= (2X^2  4X  3X + 6)  2(X^2  4X +3)\\
&= (2X^2  7X + 6)  2X^2 + 8X  6\\
&= X
\end{align}
Computational overhead of Lagrange interpolation
If done naively, interpolating $\phi(X)$ using the Lagrange formula in Equation \ref{eq:lagrangeformula} will take $O(n^2)$ time.
However, there are known techniques for computing $\phi(X)$ in $O(n\log^2{n})$ time. We described part of these techniques in a previous blog post, but for the full techniques please refer to the “Modern Computer Algebra” book^{1}.

Fast polynomial evaluation and interpolation, by von zur Gathen, Joachim and Gerhard, Jurgen, in Modern Computer Algebra, 2013 ↩