1.9

Claim. After the call horner(A,x) returns, the value stored in p equals the polynomial [math]\displaystyle{ P(x)=a_nx^{\,n}+a_{n-1}x^{\,n-1}+\dots +a_1x+a_0 }[/math].

Loop-invariant. Immediately before each execution of the body with index i (so the next statement is p = p*x + A) [math]\displaystyle{ p=\sum_{k=i+1}^{n} a_k x^{\,k-(i+1)}. }[/math>
In words, p already equals the value of the suffix polynomial that contains exactly the coefficients processed so far, divided by the power [math]x^{\,i+1}[/math].

Initialization. Before the first loop iteration we have p = a_n. Because the first index will be [math]i=n-1[/math], the right–hand side of the invariant is [math]\sum_{k=n}^{n} a_k x^{\,k-n}=a_n[/math], so the invariant holds.

Maintenance. Assume the invariant is true on entry to the iteration with a given [math]i[/math]. The assignment performs [math]\displaystyle{ p\leftarrow p\cdot x + a_i. }[/math];
Using the inductive hypothesis for [math]p[/math] we obtain
[math]\displaystyle{ p =\left(\sum_{k=i+1}^{n} a_k x^{\,k-(i+1)}\right)\!x + a_i = \sum_{k=i+1}^{n} a_k x^{\,k-i}+a_i =\sum_{k=i}^{n} a_k x^{\,k-i}. }[/math];
This is exactly the invariant for the next loop entry, where the index will be [math]i-1[/math]. Hence the invariant is preserved.

Termination. The loop stops after executing the body for [math]i=0[/math]. At that point the invariant states [math]\displaystyle{ p=\sum_{k=0}^{n} a_k x^{\,k}=P(x), }[/math]; so the algorithm returns the correct value.

Complexity. The loop performs one multiplication and one addition per coefficient, totalling [math]n[/math] multiplications and [math]n[/math] additions, i.e. [math]O(n)[/math] time and [math]O(1)[/math] extra space.

Therefore the algorithm is correct.

Back to Chapter 1 .