Difference between revisions of "TADM2E 2.5"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
 
(Corrected formatting mistakes.)
Line 1: Line 1:
(a) worst case is 2n multiplies. this will include n additions
+
(a) worst case is <math>2n</math> multiplications and <math>n</math> additions
  
(b) In any case the algorithm performs 2*n multiplications.
+
(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
  
(i) executes exactly n times.
+
# Executes exactly <math>n</math> times.
(ii) also executes n times . Even if some ai  0, it still performs
+
# 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, involves a multiplication with
+
0.
+
  
So the average number of multiplications is :  
+
So the average number of multiplications is:  
   
+
  
&lt;math&gt;(2*n + 2*n + ....(m-times)...+2*n)/m&lt;/math&gt;
+
<math>= (2*n + 2*n + ....(m-times)...+2*n)/m</math>
&lt;math&gt;=  2*n*m/m&lt;/math&gt;
+
&lt;math&gt;=  2*n&lt;/math&gt;
+
  
 +
<math>=  2*n*m/m</math>
  
 +
<math>=  2*n</math>
  
(c) There is a fast algorithm for polynomial evaulation known as [http://en.wikipedia.org/wiki/Horner's_method Horner's method]. It requires ''n'' additions and ''n'' multiplications:
+
(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:
== &lt;pre&gt;
+
res = 0;
+
for (i = n ; i &gt;= 0;i--) {
+
    res = (res * x) + aᵢ;
+
}
+
return res;
+
&lt;/pre&gt; ==
+
  
 +
  res = 0;
 +
  for (i = n ; i &gt;= 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
  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;

Return to Algo-analysis-TADM2E