TADM2E 2.5

(a) worst case is 2n multiplies. this will include n additions

(b) In any case the algorithm performs 2*n multiplications.

  for i := 1 to n do
      xpower := x * xpower;  --------- (i)
      p := p + ai * xpower     ---------(ii)
  end

(i) executes exactly n times. (ii) also executes n times . Even if some ai = 0, it still performs p := p + 0 * xpower ,which of course, involves a multiplication with 0.

So the average number of multiplications is :

<math>(2*n + 2*n + ....(m-times)...+2*n)/m</math> <math>= 2*n*m/m</math> <math>= 2*n</math>

(c) There is a fast algorithm for polynomial evaulation known as Horner's method. It requires n additions and n multiplications: == <pre> res = 0; for (i = n ; i >= 0;i--) {

   res = (res * x) + aᵢ;

} return res; </pre> ==

Return to Algo-analysis-TADM2E ...