Chapter 11.3, Problem 42ES

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

Algorithm 11.3.4 Homer’s Rule
[This algorithn computes the value of a polynomial $a\left[n\right]x^n+a\left[n-1\right]x^{n-1}+\cdots +a\left[2\right]x^2+a\left[1\right]x+a\left[0\right]$by nesting successive additions and multiplications as indicated in the following parenthesization:

   $\left(\left(\cdots \left(\left(a\left[n\right]x+a\left[n-1\right]\right)x+a\left[n-2\right]\right)x+\cdots +a\left[2\right]\right)x+a\left[1\right]\right)x+a\left[0\right]$ .

At each stage, starting with $a\left[n\right]$ , the current value of polyval is multiplied by x and the next lower coefficient of the polynomial is added to it.] Input: n[a nonnegative integer], $a\left[0\right],a\left[1\right],a\left[2\right],\dots ,a\left[n\right]$[an array of real numbers], x [a real number] Algorithm Body:
$polyval:=a\left[n\right]$for $i:=1$ to n $polyval:=polyval\cdot x+a\left[n-i\right]$ next i $\begin{array}{l}[Atthispointpolyval=a\left[n\right]x^n+a\left[n-1\right]x^{n-1}\\ +\cdots +a\left[2\right]x^2+a\left[1\right]x+a\left[0\right].]\end{array}$
Output: polyval [a real number]
42. Let $t^n=$ the number of additions and multiplications that are performed when Algorithm 11.3.4 is executed for a polynomial of degree n. Express $t^n$ , as a function of n.