Chapter Review
325
5. 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