TADM2E 2.5

(a) worst case is $ 2n $ multiplications and $ n $ additions

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

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

1. Executes exactly $ n $ times.
2. Also executes $ n $ times . Even if some ai is $ 0 $, it still performs p := p + 0 * xpower, which of course involves a multiplication with $ 0 $.

So the average number of multiplications is:

$ = (2*n + 2*n + ....(m-times)...+2*n)/m $

$ = 2*n*m/m $

$ = 2*n $

(c) There is a faster algorithm for polynomial evaluation known as Horner's method. It requires $ n $ additions and $ n $ multiplications:

 res = 0;
 for (i = n ; i >= 0;i--) {
     res = (res * x) + aᵢ;
 }
 return res;

Return to Algo-analysis-TADM2E