2-3 Correctness of Horner’s rule

You are given the coefficents $a_0; a_1; a_2; \dots; a_n$ of a polynomial $$ \begin{aligned} P(x) & = \sum_{k=0}^n a_kx^k \cr &=a_0+a_1x+a_2x^2+\cdots +a_{n-1}x^{n-1}+a_nx^n, \end{aligned} $$ and you want to evaluate this polynomial for a given value of x. Horner's rule says to evalusate the polynomial according to this > parenthesization: $$ P(x) = a_0 + x ( a_1 + x ( a_2 + \cdots + x ( a_{n-1} + x a_n) > \cdots )). $$ The procedure HORNER implements Horner**’s rule to > evaluate $P(x)$, > givem the coefficients $a_0,a_1,a_2,\dots,> a_n$ in an array $A[0:n]$ and > the value of $x$.

HORNER (A,n,x)
    p=0
    for i = n downto 0
        p = A[i] + x * p
    return p

a. In terms of $\Theta$-notation, what is the tunning time of this procedure?

b. 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 with HORNER?

c. Consider the following loop invariant for the procedure HORNER:

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

$$ p = \sum _{k=0}^{n-(i+1)} A[k+i+1] \cdot x^k $$

Interpret a summation with no terms at equaling 0. Following the structure of th loop-invariant proof presented in this chapter, use this loop invariant to show that, at termination, $p = \sum _{k=0} ^{n} A[k] \cdot x^k$

a

$\Theta(n)$

b

pseudocode:

naive_polynomia_evaluation (A,n,x)
    p=0
    for i = 0 to n
        term = A[i]
        for j = 1 to i
            term = term * x
        p = term + p
    return p

$\text{running time:} \Theta (n^2)$, HORNER beat it asymptotically.

c

Initialization: $i=n, p=\sum_{k=0}^{n-(n+1)} A[k+n+1] \cdot{x^k} = 0$, loop invariant holds.

Maintenance: in the end of each iteration:

$$ \begin{aligned} p & = A[i] + x \cdot{\sum_{k=0}^{n-(i+1)} A[k+i+1] \cdot {x^k}} \cr & = A[i] + \sum_{k=0}^{n-(i+1)} A[k+i+1] \cdot{x^{k+1}}\cr & = A[i] \cdot{x^0} + \sum_{k=1}^{n-i} A[k+i] \cdot{x^{k}}\cr & = \sum_{k=0}^{n-i} A[k+i] \cdot{x^k}\cr \end{aligned} $$

Decrementing i preserves the loop invariant.

Termination: The loop terminates at $i=−1$. If we substitute,

$$ p = \sum_{k=0}^{n-(i+1)} A[k+i+1] \cdot{x^k} = \sum_{k=0}^{n} A[k] \cdot{x^k} $$