The following code fragment implements Horner\'s rule for evaluating a polynomia
ID: 3814849 • Letter: T
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.