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

\[\begin {aligned} P(x) & = \sum _{k = 0}^n a_k x^k \\ & = a_0 + x(a_1 + x(a_2 + \cdots + x(a_{n - 1} + xa_n) \cdots)) \end {aligned}\]given the coefficients \(a_0, a_1, \ldots , a_n\) and a value for \(x\):

$$\begin{aligned}1& \quad y=0 \\2& \quad \textbf {for }i=n\textbf { downto }0 \\3& \quad \qquad y=a_{i}+x\cdot\,\,y \\\end{aligned}$$

- In terms of \(\Theta\) 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 = \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1}x^k\]Interpret a summation with no terms as equaling 0. Following the structure of the loop invariant proof presented in this chapter, use this loop invariant to show that, at termination, \(y = \sum_{k = 0}^n a_k x^k\).

- Conclude by arguing that the given code fragment correctly evaluates a polynomial characterized by the coefficients \(a_0, a_1, \cdots , a_n\).

#### A. 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 \(\Theta(n)\) time.

#### B. Comparison with Naive Algorithm

We can write the pseudocode as follows, where \(A\) is an array of length \(n + 1\) consisting of the coefficients \(a_0, a_1, \ldots , a_n\).

The above algorithm runs with a **for** loop of \((n - 1)\) elements (lines 4-5) inside another **for** loop (lines 2-6) of \(n\) elements. Therefore, the algorithm runs at \(\Theta(n^2)\) time.

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

#### C. Loop Invariant Analysis

**Initialization:** At the start of the first iteration, there are no terms in the summation, so the sum is zero.

**Maintenance:** From the loop invariant, for any arbitrary \(0 \leq i < n\), at the start of the \(i\)-th iteration of the **For** loop of lines 2-3, \(y = \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1}x^k\)

Now, after the \(i\)-th iteration, as we are iterating from \(n\) **downto** \(0\), we will have \(i = i - 1\). So, to prove the maintenance of the loop invariant, we’ll need to show that after the \(i\)-th iteration, we will have \(y = \sum_{k = 0}^{n - ((i - 1) + 1)} a_{k + (i - 1) + 1}x^k = \sum_{k = 0}^{n - i} a_{k + i}x^k\).

This can be shown as follows…

\[\begin {aligned} y' & = a_i + x \cdot y \\ & = a_i + x \cdot \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1}x^k \\ & = a_i + \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1}x^{k + 1} \\ & = \textcolor{blue} {a_ix^0} + a_{i+1}x^1 + a_{i+2}x^2 + \cdots + a_nx^{n-i} \\ & = \sum_{k=0}^{n-i} a_{k+i} x^k \end {aligned}\]**Termination:** When the loop terminates, we have \(i = -1\). So,

This is precisely what we wanted to calculate.

#### D. Correctness Argument

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