Correctness of Horners rule The following code fragment

Chapter 2, Problem 2-3

(choose chapter or problem)

Correctness of Horners rule The following code fragment implements Horners rule for evaluating a polynomial P .x/ D Xn kD0 akxk D a0 C x.a1 C x.a2 CC x.an1 C xan/// ; given the coefficients a0; a1;:::;an and a value for x: 1 y D 0 2 for i D n downto 0 3 y D ai C x y a. In terms of -notation, what is the running time of this code fragment for Horners 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 Horners rule? c. Consider the following loop invariant: At the start of each iteration of the for loop of lines 23, y D n X .iC1/ kD0 akCiC1xk : Interpret a summation with no terms as equaling 0. Following the structure of the loop invariant proof presented in this chapter, use this loop invariant to show that, at termination, y D Pn kD0 akxk. d. Conclude by arguing that the given code fragment correctly evaluates a polynomial characterized by the coefficients a0; a1;:::;an. 2-4 Inv