Difference between revisions of "TADM2E 2.5"

(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

1. Executes exactly $n$ times.
2. 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;