Given the points (x0, y0),(x1, y1), . . . ,(xn, yn), we want to find the polynomial Pn(x) of degree n that goes exactly through them. We know that given a point x, a polynomial that goes through the points (xi , yi), . . . ,(xj , yj) is given by the following recursive formula Pi,j (x) = (xj x)Pi,j1(x) + (x xi)Pi+1,j (x) / xj xi

(a) Notice that Pk,k is a polynomial of degree 0 (constant) that goes exactly through point (xk, yk). What is Pk,k(x) =

(b) Provide a dynamic programming algorithm to compute P0,n(x)

(c) What is the time complexity of your algorithm?