Correctness of Horner’s RuleThe following code fragment implements Horner’s rule for evaluating a polynomial

given the coefficients and a value for :

`1 y = 0 2 for i = n downto 0 3 y = a_i + x * y`

- In terms of -notation, what is the asymptotic running time of this code fragment for Horner’s rule?
- Write pseudocode 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?
- Consider the following loop invariant:. At the start of each iteration of the for loop of lines 2-3, Interpret a summation with no terms as equaling 0. Your proof should follow the structure of the loop invariant proof presented in this chapter and should show that, at termination, .
- Conclude by arguing that the given code fragment correctly evaluates a polynomial characterized by the coefficients .

**1. Asymptotic Running Time**

From the pseudocode of Horner’s Rule, the algorithm runs in a loop for all the elements, i.e. it runs at time.

**2. Comparison with Naive Algorithm**

Pseudocode for `NAIVE-POLY-EVAL(A, x)`

, where is the array of length consisting of the coefficients .

```
y = 0
for i = 1 to A.length
m = 1
for j = 1 to i - 1
m = m * x
y = y + A[i] * m
```

The above algorithm runs with for inside another for loop multiplications to evaluate and $(n - 1)$ additions in total to evaluate a polynomial. Hence, it does multiplications and additions. Therefore, the algorithm runs at time.

This algorithm is obviously worse than Horner’s rule which runs at linear time.

**3. Loop Invariant for the While Loop**

**Initialization:** At the start of the first iteration, we have . So,

As the sum is zero, the loop invariant holds after the first loop.

**Maintenance:** From the loop invariant, for any arbitrary , at the start of the -th iteration of the while loop of lines 3–5,

Now, after the -th iteration,

So, the loop invariant also holds after the loop.

We make two assumption:

- : This is valid as is nothing but the summation parameter.
- : This holds as this is precisely the operation done in line 5.

**Termination:** When the loop terminates, we have . So,

This is precisely what we wanted to calculate.

**4. Correctness Argument**

When Horner’s rule terminates it successfully evaluates the polynomial as it intended to. This means the algorithm is correct.