5. (20 points) Compare two algorithms: Exercise 13, p. 230 (conventional algorit

Question

5. (20 points) Compare two algorithms: Exercise 13, p. 230 (conventional algorithm), and Exercise 14, p. 230 (Horner's method). . A pseudocode for the conventional algorithm for evaluating a polynomial anz" +an-lz"- ·· procedure polynomial(c, ao, a1,..., an : real numbers) p := 1 {power} for i := 1 to n p:= p*c y := y + ai*p return y . A pseudocode called Horner's method for evaluating a polynomial anan-1"-1+...+a1r+ao procedure Horner(c, ao, a1,a2,... . an: real numbers) 72 for i := 1 to n return y (a) Evaluate 3x2 + x + 1 at x = 2 by working through each step of the conventional and Horner's algorithms showing the values assigned at each step. (b) Exactly how many multiplications and additions are used by the conventional and the Horner's algorithm to evaluate a polynomial of degree n at r - c. Express the number of multiplications and additions as a function of n. (Do not count additions used to increment the loop variable.) (c) Classify the algorithms for evaluating polynomials using big-O asymptotic notation.

Explanation / Answer

a) 3x^2 + x + 1 at x = 2

   First alogorithm :
        loop = 1     p=2 y = 3
        loop = 2     p = 4 y =15
       

   Secnd alogorithm :
        loop = 1     y = 7
        loop = 2     y = 15
       

b)   First algorithm - Multiplication - 4 , Addition - 2
     Second algorithm - Multiplication - 2 , Addition - 2

c) The order of complexity in both the cases is O(n) because the loop is running for n times.

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

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