Correctness of Horner’s Rule
The 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,
\[\begin {aligned} y & = \sum_{k = 0}^{n - (i + 1)} a_{k + i + 1}x^k \\ & = \sum_{k = 0}^{n - (-1 + 1)} a_{k - 1 + 1}x^k \\ & = \sum_{k = 0}^n a_k x^k \end {aligned}\]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.