The following algorithms evaluate the polynomial p(x) = a_nx^n + a_n-1x^n-1 + ..

Question

The following algorithms evaluate the polynomial p(x) = a_nx^n + a_n-1x^n-1 + ...+a_1 x + a_0 at a point x = c in two different ways. procedure polynomial(c, a_0, a_1, ..., a_n) power:= 1 y =a_0 for i:= 1 to n power:= power * c y:=y + a_i * power return y procedure Horner(c, a_0, a_1, ..., a_n) y:=a_n for i:= 1 to n y:= y * c + a_n-i return y Evaluate 3x^2 + x + 1 at x = 2 using each of the two procedures. Show your steps. Exactly how many multiplications and additions are used by each of the two procedures for a polynomial of degree n at x = c? (Do not count additions used to increment for-loops). Which procedure is more efficient?

Explanation / Answer

3*x2 + x + 1 at x = 2

a) polynomial ( 2 , 1 ,1 ,3 )
y = 1
Step 1 : i = 1
y = 1 + 1*2
y = 3
Step 2 : i = 2
y = 3 + 3*4
y = 15



b) Horners ( 2 , 1 ,1 ,3 )
y = 3
Step 1 : i = 1
y = 1 + 3*2
y = 7
Step 2 : i = 2
y = 1 + 7*2
y = 15




b) . Both the procedure takes O(n) times , But the number of multiplication required in polynomial is more than number of multiplication in Horners.



Multiplication by Polynomial . : 2n multiplications
Multiplication by Horners : n multiplications


Thanks, let me know if there is any concern.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.