SOLVE BOTH PARTS A AND B.

HINT: parts (a) and (b). Note: the running time is the number of elementary operations (additions and multiplications) needed. Thus, to compute the cube of x you need two multiplications: x times x times x.

2-3 Correctness of Horner's rule The following code fragment implements Horner's rule for evaluating a polynomial given the coefficients ao, a1,.... an and a value for x: 1 y=0 2 for i= n downto 0 a. In terms of -notation, what is the running time of this code fragment for Horner's rule? b. Write pseudocode to implement the naive polynomial-evaluation algorithm that computes each term of the polynomial from scratch. What is the running time of this algorithm? How does it compare to Horner's rule