Chapter Review 325
- Find the complexity for each of the following algorithms that evaluate a polynomial of
degree n at a value x0. Assume multiplication is the key operation.
a.
INPUT: n c N, the coefficients of P stored in a[O. .n], and a real number x0
OUTPUT: P(x0)
Poly = a [0]
x=1
for/= 1 to n
X =-X0 - X
Poly = a[i] ā¢ x + Poly
print Poly
b.
INPUT: n E Nā¢ and a real number x0 and the coefficients of a polynomial of degree n
stored in a [0. .n]
OUTPUT: P(xo)
Poly = a[01
fori =0ton
x=l
for j = 1 to i
X = X X0
Poly = Poly + a[i] -x
print Poly
