4 For the polynomial fx 3x22x 1 and the value of x 1 list

4. For the polynomial f(x) = 3x^2+2x + 1 and the value of x = 1, list in order the successive values of S that occur in the calculation of f(x) by i. the algorithm described in Problem 2 Step 1.Set P= 1 Step 2. for i =1 to n, replace P by Px, call this element xi and store (note that xi = xi); Step 3. set S = a0; Step 4. For i=1 to n, replace S by S +aixi; Step 5. output S. ii. Homer?s Algorithm 1. Find the complexity function of the algorithm you described in question 3 above.

Solution

1.

P = 1

S = 1

P = X = 1 = X1

S = S+a1x1 = 1+2*1 = 3

P = x^2 = 1 = x2

S = 3+a2x2 = 3+3*1 = 6

__________________________________________________________

Horner\'s rule

P2 = a2 = 3

P1 = (P2)x+a1 = 3*1+2 = 5

P0 = (P1)x+a0 = 5*1+1 = 6

_______________________________________________________-

what is question 3 for which you are asking complexity.

and by the way complexity of horner\'s algo is O(n).