**Correctness of Horner’s rule**

You are given the coefficients of a polynomial

and you want to evaluate this polynomial for a given value of x. Horner’s rule says to evaluate the polynomial according to this parenthesization:

The procedure HORNER implements Horner’s rule to evaluate P(x), given the coefficients in an array and the value .

- In terms of \Theta-notation, what is the running time of this procedure?

- 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 with HORNER?

- Consider the following loop invariant for the procedure HORNER:
At the start of each iteration of the
**for**loop of lines 2-3, Interpret a summation with no terms as equaling 0. Following the structure of loop invariant proof presented in this chapter, use this loop invariant to show that, at termination,