$(20$ pts$.)$ Polynomial computation analysis. Suppose we want to evaluate the polynomial

$p(x)=a_0+a_{1}x+a_2{x}^2+$cdots$+a_n{x}^n$

at some point $x_0.$

$($a$)$ Consider the algorithm that computes first $x_0^i$ for each $i,$ using the fast exponentiation algorithm from lectures $($without taking mod$).$ Then, it computes $a_1{x}_0,a_2{x}_0^2,a_3{x}_0^3,$dots,$a_n{x}_0^n($independently$)$ and, finally, it adds all of these numbers to $a_0$ to obtain $p(x_0).$ How many sums and how many multiplications are involved in this algorithm? Please provide short explanations. $($You can give your answer in $O-$notation.$)$

$($b$)$ We show next how to do better using Horner's rule. Prove that the following algorithm outputs $p(x_0).$

Algorithm $1$ Horner's rule

$z=a_n$

for $i=n-1$ to $0$ do:

$z=z*x_0+a_i$

end for

return $z$

CMPSC $465,$ Spring $2024,$ HW $2$

$1$

$($c$)$ How many additions and multiplications does this algorithm use as a function of $n?$ Please provide short explanations. $($You can give your answer in $O-$notation.$)$