# TADM2E 2.5

From Algorithm Wiki

(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

- Executes exactly $ n $ times.
- 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