Problem 2-3 Correctness of Horner’s rule The following code fragment implements Horner’s r

[shweta14]

Problem 2-3 Correctness of Horner’s rule The following code fragment implements Horner’s rule for evaluating a polynomial
P(x) = En a^X^k
k=0o

= a0 + x(a1 + x(a2 +· · · + x(an−1 + xan) · · ·)) ,
given the coefficients a0, a1, . . . , an and a value for x:
1 y ← 0
2 i ← n
3 while i ≥ 0
4 do y ← ai + x · y
5 i ←i − 1
a. What is the asymptotic 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?
c. Prove that the following is a loop invariant for the while loop in lines 3 –5.
At the start of each iteration of the while loop of lines 3–5,
y = n−(i+1) E ak+i+1xk .
k=0

Interpret a summation with no terms as equaling 0. Your proof should follow the structure of the loop invariant proof presented in this chapter and should
show that, at termination, y = En k=0 akxk .
d. Conclude by arguing that the given code fragment correctly evaluates a polynomial characterized by the coefficients a0, a1, . . . , an.