Question

Let pn interpolate f at n + 1 distinct points. Consider pn in its Lagrange and Newton forms

$pn(x) = \sum_{j = 0}^{n}a_{j} \prod_{k=0,k != j}^{n} (x-x_{k}) = \sum_{j = 0}^{n}c_{j} \prod_{k=0}^{j-1} (x-x_{k})$

with $a_{j} = f(x_{j}) \prod_{k = 0, k != j}^{n} \frac{1}{(x_{j}- x_{k})}$    and

Suppose that we will evaluate pn many times for different values of x. Thus, we can precompute the values of aj and cj and then can use them without any cost. For both forms, propose efficient (in terms of arithmetic operations) algorithms for computing pn(x). Which form admits less expensive algorithm?