Use the theorem on polynomial orders to find an order for Algorithm 11.3.4. How does

Chapter 11, Problem 43

(choose chapter or problem)

Exercises 40-43 refer to another algorithm, known as Horner's rule, for finding the value of a real polynomial.

Algorithm 11.3.4 Horner's Rule

[This algorithm computes the value of the real polynomial \(a[n] x^{n}+a[n-1] x^{n-1}+\cdots+a[2] x^{2}+a[1] x+a[0]\) by nesting successive additions and multiplications as indicated in the following parenthesization:

\(((\cdots((a[n] x+a[n-1]) x+a[n-2]) x\)

\(+\cdots+a[2]) x+a[1]) x+a[0]\)

At each stage, starting with a[n], the current value of polyval is multiplied by x and the next lower coefficient of the polynomial is added on.J

Input: n [a nonnegative integer] \(a[0], a[1], a[2], \ldots, a[n]\) [an array of real numbers], x [a real number]

Algorithm Body:

polyval : = a[n]

for i:=1 to n

polyval := polyval \(\cdot x+a[n-i]\)

next i

[At this point

polyval \(=a[n] x^{n}+a[n-1] x^{n-1}\)

\(\left.+\cdots+a[2] x^{2}+a[1] x+a[0] .\right]\)

Output: polyval [ a real number]

Use the theorem on polynomial orders to find an order for Algorithm 11.3.4. How does this order compare with that of Algorithm 11.3.3?

Text Transcription:

a[n] x^n+a[n-1] x^n-1+dots+a[2] x^2+a[1] x+a[0]

((dots((a[n] x+a[n-1]) x+a[n-2]) x

+\cdots+a[2]) x+a[1]) x+a[0]

a[0], a[1], a[2], \ldots, a[n]

dot x+a[n-i]

=a[n] x^n+a[n-1] x^n-1

+\cdots+a[2] x^{2}+a[1] x+a[0]