You are given the coefficients $\backslash$alpha $0,\backslash$alpha $1,...,\backslash$alpha n of a polynomial

P$($x$)=$ Xn k$=0\backslash$alpha kxk$=\backslash$alpha $0+\backslash$alpha $1$x $+\backslash$alpha $2$x

$2++\backslash$alpha nx

n

$,$

and you want to evaluate this polynomial for a given value of x$.$ Horner$$s rule says to

evaluate the polynomial according to this parenthesization:

P$($x$)=\backslash$alpha $0+$ x

$\backslash$alpha $1+$ x

$\backslash$alpha $2++$ x $(\backslash$alpha n$1+$ x$\backslash$alpha n$)$

$.$

The procedure Horner implements Horner$$s rule to evaluate P$($x$),$ give the coefficients

$\backslash$alpha $0,\backslash$alpha $1,...,\backslash$alpha n in an array A$[0$ : n$]$ and the value of x$.$

Horner$($A$,$ n$,$ x$)$

$1$: p $0$

$2$: for i $=$ n to $0$ do

$3$: p $$ A$[$i$]+$ x $$ p

$4$: end for

$5$: return p

For this problem, assume that addition and multiplication can be done in constant time.

$($a$)$ In terms of $\backslash$Theta $-$notation, what is the running 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 to Horner?

$($c$)$ Consider the following loop invariant for the prcedure Horner:

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

p $=$

n$$X

$($i$+1)$

k$=0$

A$[$k $+$ i $+1]$ x

k

$.$

Interpret a summation with no terms as equaling $0.$ Following the structure of the loopinvariant proof presented in class, use this loop invariant to show that, at termination,

p $=$Pn k$=0$ A$[$k$]$ xk$.$