Question

There is a more efficient algorithm (in terms of the number of multiplications and additions used) for eval- uating polynomials than the conventional algorithm de- scribed in the previous exercise. It is called Horner’s method. This pseudocode shows how to use this method

to find the value ofat x = c .a_{n} * x ^ n +a n-1 x^ n-1 +*+a 1 x+a 0
procedure Horner(c,a_{0}, a_{1}, a_{2} ,...,a nreal numbers)
y :=a n
for i :=1 to n
y:=y*c+a n - ireturn y {y = a,c"+a-1c"-1++ a₁c + αo}
a) Evaluate 3x ^ 2 + x + 1 at x = 2 by working througheach step of the algorithm showing the values as-signed at each assignment step.
b) Exactly how many multiplications and additions areused by this algorithm to evaluate a polynomial ofdegree n at x =c? (Do not count additions used toincrement the loop variable.)

Answer 1

The polynomial 3x^2 + x + 1 is evaluated at x = 2 using Horner's method, resulting in a value of 15. Horner's method requires n multiplications and n additions for a polynomial of degree n.

Step-by-step explanation:

To evaluate the polynomial 3x^2 + x + 1 at x = 2 using Horner's method, we use the given pseudocode and follow the algorithm step by step:

1. Let y be initially equal to the coefficient of the highest degree term, which is the coefficient of x^2. So, y = 3.
2. Now, multiply y by c (which is 2 in this case) and add the coefficient of the next lower degree term, the coefficient of x. Then, y = (3*2) + 1 = 7.
3. Repeat the process for the next term. Multiply y by c (which is 2) and add the constant coefficient, which is a_0. So, y = (7*2) + 1 = 15.

Therefore, y = 15 is the value of the polynomial at x = 2.

Regarding the number of operations, Horner's method uses n multiplications and n additions to evaluate a polynomial of degree n at x = c, assuming that we do not count the incrementation of the loop variable.