The following code fragment implements Horner’s rule for evaluating a polynomial

\[\begin{align*} P(x) &= \sum\limits_{k=0}^{n} \\ &= a_0 + x(a_1 + \cdots + x(a_{n-1} + xa_n) \cdots)) \\ \end{align*}\]

given the coefficients \(a_0, a_1,...,a_n\) and a value for x:

1 y = 0

2 for i = n downto 0

3      y = aᵢ + x · y

a. In terms of \(\Theta\)-notation, what is the running time of this code fragment for Horner’s rule?

\(\Theta (n)\). All we are doing is performing the action on line 3 \(n\) times.

b. Write pseudocode to implement the naive polynomail-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?

1 y = 0

2 for i = 0 to n

3      term = aᵢ

4      for j = 1 to i

5          term = term · x

6      y = y + term

This algorithm runs at \(\Theta (n^2)\) due to the nested loop. It is not as efficient as Horner’s rule.

c. Consider the following loop invariant:

At the start of each iteration of the for loop of lines 2-3,

\(y = \sum\limits_{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_kx^k\).

Inititialization: Before the first loop iteration, the summation has no terms, and so (trivially) \(y = 0\).

Maintenance: After the loop iterates, we have \(y' = a_i + x · y\). Since \(i\) is decrementing, \(y' = \sum\limits_{k=0}^{n-i}a_{k+i}x^k\) and based on the loop invariant, \(y = \sum\limits_{k=0}^{n-(i+1)}a_{k+i+1}x^k\). So we have:

\[\begin{align*} y' &= a_i + x · y \\ \sum\limits_{k=0}^{n-i}a_{k+i}x^k &= a_i + x · \sum\limits_{k=0}^{n-(i+1)}a_{k+i+1}x^k \\ \sum\limits_{k=0}^{n-i}a_{k+i}x^k &= a_ix^0 + \sum\limits_{k=0}^{n-(i+1)}a_{k+i+1}x^k+1 \\ \sum\limits_{k=0}^{n-i}a_{k+i}x^k &= a_ix^0 + \sum\limits_{k=1}^{n-i}a_{k+i}x^k \\ \sum\limits_{k=0}^{n-i}a_{k+i}x^k &= \sum\limits_{k=0}^{n-i}a_{k+i}x^k \\ \end{align*}\]

The trickiness going on here is modifying the summation’s bottom term from \(k = 0\) to \(k = 1\) which results in subtracting one from each use of the term \(k\) to keep equality. By doing this, we are then able to slide our new term \(a_ix^0\) into the summation to then return the starting \(k\) value back to \(0\). Ultimately this shows that the loop invariant holds after each iteration of the loop.

Termination: The loop terminates when \(i = -1\) at which point we have:

\[\begin{align*} y &= \sum\limits_{k=0}^{n-(i+1)}a_{k+i+1}x^k \\ &= \sum\limits_{k=0}^{n-(-1 + 1)}a_{k - 1 + 1}x^k \\ &= \sum\limits_{k=0}^{n}a_{k}x^k\\ \end{align*}\]

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

As proven above in c, Horner’s Rule is a correct algorithm that evaluates the given polynomial at termination.