# Difference between revisions of "TADM2E 2.5"

From Algorithm Wiki

(Corrected formatting mistakes.) |
m (Standardized code formatting.) |
||

Line 22: | Line 22: | ||

res = 0; | res = 0; | ||

− | for (i = n ; i >= 0;i--) { | + | for (i = n; i >= 0; i--) { |

res = (res * x) + aᵢ; | res = (res * x) + aᵢ; | ||

} | } |

## Latest revision as of 00:04, 20 June 2017

(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