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,