# 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