**2-3 Correctness of Horner’s rule**
The following code fragment implements Horner’s rule for evaluating a polynomial

$$ \begin {align}
P(x) & = \sum _{k = 0}^n a_k x^k \\
& = a_0 + x(a_1 + x(a_2 +· · · + x(a_{n − 1} + xa_n) · · ·))
\end {align} $$

given the coefficients a 0 ; a 1 ; : : : ; a n and a value for x:

y = 0
for i = n downto 0
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,
y=∑n−(i+1)k=0ak+i+1xk
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, y=∑nk=0akxk.
- Conclude by arguing that the given code fragment correctly evaluates a polynomial characterized by the coefficients a0,a1,...,an.

**Solution:**
**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

Θ(n) time.

**2. Comparison with Naive Algorithm**
Pseudocode for

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

, where

A is the array of length

n+1 consisting of the coefficients

a0,a1,...,an.

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

j multiplications to evaluate

ajxj and $(n - 1)$ additions in total to evaluate a polynomial. Hence, it does

∑nj=0j=n(n+1)/2 multiplications and

(n−1) additions. Therefore, the algorithm runs at

Θ(n2)
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

i=n. So,

y=∑k=0n−(i+1)ak+i+1xk=∑k=0n−(n+1)ak+n+1xk=∑k=0−1ak+n+1xk=0

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

**Maintenance:** From the loop invariant, for any arbitrary

0<=i<n
, at the start of the

i-th iteration of the while loop of lines 3–5,

y=∑n−(i+1)k=0ak+i+1xk
Now, after the

i-th iteration,

y′=ai+x⋅y=ai+x⋅∑k=0n−(i+1)ak+i+1xk=aix0+∑k=0n−(i+1)ak+i+1xk+1=∑k=−1n−(i+1)ak+i+1xk+1=∑k′=0n−(i+1)ak′+ixk′=∑k′=0n−(i′+1)ak′+i′+1xk′

So, the loop invariant also holds after the loop.

We make two assumption:

- k′=k+1 : This is valid as k is nothing but the summation parameter.
- i′=i−1 : This holds as this is precisely the operation done in line 5.

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

i=−1. So,

y=∑k=0n−(i+1)ak+i+1xk=∑k=0n−(−1+1)ak−1+1xk=∑k=0nakxk

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.