# TADM2E 2.5

From Algorithm Wiki

Revision as of 18:14, 11 September 2014 by Algowikiadmin (Talk | contribs)

(a) worst case is 2n multiplies. this will include n additions

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

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

(i) executes exactly n times. (ii) also executes n times . Even if some ai = 0, it still performs p := p + 0 * xpower ,which of course, involves a multiplication with 0.

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 fast algorithm for polynomial evaulation known as Horner's method. It requires *n* additions and *n* multiplications:
== <pre>
res = 0;
for (i = n ; i >= 0;i--) {

res = (res * x) + aᵢ;

} return res; </pre> ==

Return to Algo-analysis-TADM2E ...