Section 3.3 Analysis of Algorithms
213
6. Analyze the following algorithm where the work unit is the output statement. (Hint: One of the exercises
in Section 2.2 might be helpful).
integer i
real d, x;
for i = 1 to n do
d = 1.0/i;
x = i;
while x > 0 do
write x
x = x − d;
end while
end for
Exercises 7 and 8 involve n! = n(n − 1)(n − 2) c 1.
7. a. Write the body of an iterative function to compute n! for n ≥ 1.
b. Analyze this function where the work unit is the multiplication operation.
8. a. Write a recursive function to compute n! for n ≥ 1.
b. Write a recurrence relation for the work done by this function where multiplication is the unit of work.
c. Solve the recurrence relation of part b.
d. Compare your answer in part c to your result in Exercise 7b.
Exercises 9 and 10 involve evaluating a polynomial a n x
n
+ a n−1 x
n−1
+ c + a 0 for a specific value of x.
9. A straightforward algorithm to evaluate a polynomial is given by the following function:
Poly(real a n , real a n−1 , … , real a 0 , real c, integer n)
//evaluates polynomial a n x
n
+ a n−1 x
n−1
+ c + a 0
for x = c
Local variables:
integer i
real sum = a 0
real product = 1
for i = 1 to n do
product = product * c
sum = sum + a i * product
end for
return sum
end function Poly
a. Walk through this algorithm to compute the value of 2x
3
− 7x
2
+ 5x − 14 for x = 4.
b. The algorithm involves both additions and multiplications; analyze this algorithm where those operations
are the work units.
10. An alternative to the polynomial evaluation algorithm in Exercise 9 is an algorithm called Horner’s
method. Horner’s method relies on an alternative expression for a polynomial, for example
2x
3
− 7x
2
+ 5x − 14 = −14 + x(5 + x(−7 + x(2)))