3. (24 pts.) Evaluating Polynomials Consider a polynomial given by p(x)=a0+a1x+a2x2++anxn. Consider the problem of evaluating it at some point x0, i.e. computing p(x0). (a) (4pt) The naive algorithm computes independently each of the terms a1x0,a2x02,a3x03,,anx0n and then adds all of these numbers to a0 to obtain p(x0). How many sums and how many multiplications are used by this algorithm, as a function of n ? (You can give your answer in O-notation.) (b) (4pt) Now consider the following algorithm, which is claimed to also compute p(x0). \begin{tabular}{l} \hline \hline=an; \\ for i=n1 to 0 do \\ 1z=zx0+ai; \\ end \\ return z; \end{tabular} Lets get some intuition of why this algorithm is correct by seeing what happens to the values of z at each iteration for n=5. Let k be the number of the iteration that is about to start, let zk be the value of z at the start of the kth iteration, and let ik be the value of i prior to the start of the kth iteration. Complete the following table by giving the values of z3 and z4. (c) (12pt) Use the loop invariant technique to give a proof of why this algorithm is correct. (d) (4pt) How many additions and multiplications does this algorithm use as a function of n ? (You can give your answer in O-notation.)