Question

1. (2 pts each) Consider the following algorithm:

procedure polynomial(c, a0,a1,…an: real numbers)
power≔1
y≔a₀
for i=1 to n
  power≔power*c
y≔y+a_i*power
return y
(Note: y=a_ncⁿ + a_n-1 c^n-1 +. . . + a₁C +a₀ so the final value of y is the value of the polynomial at x=c)

a. Use the algorithm to calculate f(3), where f(x)=2x²+3x+1 at x=3. Show the steps of working through the algorithm – don’t just plug 3 in for x in f(x).

b. How many multiplications and additions are needed to evaluate a polynomial of degree n at x=c?

Answer 1

a)

We have to calculate f(x) = 2x² + 3x +1 at x = 3.

So here we get, a₀ = 1 , a₁ = 3 , a₂ = 2 & c = 3.

From the algorithm;

Step 1 (Initialization) :

Here we initialize the values as follows :

Step 2 (Iteration ( i = 1, 2)) :

In each iterative steps, the value of "power" and "y" are updated. The new value of "power" is assigned as the previous value of power multiplied with "c" and the value of "y" is assigned to be "y_previous+ a_i*power".

For i = 1 ;

For i = 2 ;

Step 3 :

return y

i.e. return 28

Therefore, f(3)=28, where f(x)=2x²+3x+1 at x=3.

b)

Observe the algorithm only performs addition and multiplication in step 2 (Iteration) i.e.

power≔power*c
y≔y+a_i*power

Here we see, there are 2 muliplication "power*c" and "a_i*power" and 1 addition "y≔y+a_i*power" per each iteration.

Since there can be "n" number of iterations for a n-degree polynomial as "i" can take values from 1 to n,

The number of multiplication performed = 2n

The number of addition performed =n