## Question-64

**Question-64**

** **There is a more efficient algorithm (in terms of the number of multiplications and additions used) for evaluating polynomials than the conventional algorithm. It is called **Horner’s method**. This pseudocode shows how to use this method to find the value of *anxn*+*an*−1*xn*−1+⋅⋅⋅+*a*1*x*+*a*0 at *x*=*c*.

**procedure** *Horner*(*c*,*a*0,*a*1,*a*2,…,*an*: real numbers)

*y*≔*an*

for*i*≔1to*n*

*y*≔*y** *c*+*an*−*i*

return*y*{*y*=*ancn*+*an*−1*cn*−1+⋅⋅⋅+*a*1*c*+*a*0}

**a) **Evaluate 9*x*2+2*x*+3 at *x*=2 by working through each step of the algorithm showing the values assigned at each assignment step.

y = ?

i = ?

y = ?

i = ?

y = ?

**
b)** Exactly how many multiplications and additions are used to evaluate a polynomial of degree

*n*at

*x*=

*c*? (Do not count additions used to increment the loop variable.)

There are = ?

There are = ?

**Solution**

**a) **

y = 9

i = 1

y = 20

i = 2

y =43

**b)**

There are = n multiplications.

There are = n additions.