The following code fragment implements Horner?s rule for evaluating a polynomial The following code fragment implements Horner?s
Question:
The following code fragment implements Horner?s rule for evaluating a polynomial The following code fragment implements Horner?s rule for evaluating a polynomial
given the coefficients a0, a1??.,an and a value for x:
1.?y?=?0
2. For i = n downto 0
3.?y?=?ai + x ? y
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?
c. Consider the following loop invariant: 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 the loop invariant proof presented in this chapter, use this loop invariant to show that, at termination,
d. Conclude by arguing that the given code fragment correctly evaluates a polynomial characterized by the coefficients a0, a1,....,an.
Step by Step Answer:
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest