Difference between revisions of "TADM2E 2.5"
From Algorithm Wiki
(Recovering wiki) |
(Corrected formatting mistakes.) |
||
| Line 1: | Line 1: | ||
| − | (a) worst case is 2n | + | (a) worst case is <math>2n</math> multiplications and <math>n</math> additions |
| − | (b) In any case the algorithm performs | + | (b) In any case the algorithm performs <math>2n</math> multiplications. |
for i := 1 to n do | for i := 1 to n do | ||
| Line 8: | Line 8: | ||
end | end | ||
| − | + | # Executes exactly <math>n</math> times. | |
| − | + | # Also executes <math>n</math> times . Even if some '''ai''' is <math>0</math>, it still performs '''p := p + 0 * xpower''', which of course involves a multiplication with <math>0</math>. | |
| − | p := p + 0 * xpower ,which of course | ||
| − | 0. | ||
| − | So the average number of multiplications is : | + | 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 | + | (c) There is a faster algorithm for polynomial evaluation known as [http://en.wikipedia.org/wiki/Horner's_method Horner's method]. It requires <math>n</math> additions and <math>n</math> multiplications: |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| + | res = 0; | ||
| + | for (i = n ; i >= 0;i--) { | ||
| + | res = (res * x) + aᵢ; | ||
| + | } | ||
| + | return res; | ||
| − | Return to [[Algo-analysis-TADM2E]] | + | Return to [[Algo-analysis-TADM2E]] |
Revision as of 13:40, 13 September 2015
(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
