Correct, well explained answers will be given a thumbs up!

3. (20 pts.) Polynomials and Horner's rule (HW) Suppose we want to evaluate the polynomial p(x) do+ajx+a2x2 + ... + ant" at some point xo. (a) Consider the brute force algorithm that computes first ajx0, 42x7, 23x,...,anx (independently) and then adds all of these numbers to do to obtain p(xo). How many sums and how many multiplications are involved? (You can give your answer in O-notation.) (b) We show next how to do better using Horner's rule. Prove that the following algorithm outputs p(xo). Use the loop invariant proof structure we saw in class. z=ani for i=n-1 to 0 do | z=z-X0 +07: end return z: (c) How many additions and multiplications does this algorithm use as a function of n? (You can give your answer in O-notation.)