Difference between revisions of "TADM2E 2.5"
From Algorithm Wiki
(Recovering wiki) 
(No difference)

Revision as of 18:14, 11 September 2014
(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 + ....(mtimes)...+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 AlgoanalysisTADM2E ...