The following code fragment implements Horner\'s rule for evaluating a polynomia

Question

The following code fragment implements Horner's rule for evaluating a polynomial P(x) = sigma^n_k=0 a_k x^k = a_0 + x (a_1 + x(a_2 + ... + x(a_n-1 + xa_n)...)), given the coefficients a_0, a_1, ... a_n and a value for x: 1: y = 0 2: for i = n down to 0 do 3: y = a_i + x * y 4: end for 1. In terms of theta-notation, what is the running time of this code fragment for Horner's rule? 2. Write pseudo-code to implement the naive polynomial evaluation algorithm that computes each term of the polynomial from scratch. What is the running time of this algorithm? How does it compare to Horner's rule?

Explanation / Answer

1. (n).

2. Pseudo Code

The running time is (n2), because of the nested loop. It is, obviosly, slower.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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