Chapter Review 53
9.12.4 Using Discrete Mathematics in Computer Science
- Find a recurrence relation for the sum of the first n natural numbers for any n E N.
Solve the recurrence relation. (This closed form represents the complexity of selection
sort that was described in Section 1.7.1.)
- (a) Find a recurrence relation to describe the complexity of the recursive code to com-
pute a' for any positive real number a and any natural number n:
INPUT: a E R with a > 0 and n E N
OUTPUT: an
recursivePower(a, n)
if n = 0 then
recursivePower(a, n) = 1
else
recursivePower(a, n) = a • recursivePower(a, n - 1)
(b) Find a closed form for the function found in part (a).
- (a) Find a recurrence relation to describe the complexity of the recursive code for
computing the nth Fibonacci number:
INPUT: n E N
OUTPUT: Fn
recursiveFibonacci(n)
if n = 0 then
recursiveFibonacci(O) = 1
else
if n = 1 then
recursiveFibonacci(1) = 1
else
recursiveFibonacci(n) = recursiveFibonacci(n - 1)
+ recursiveFibonacci(n - 2)
(b) Find a closed form for the function found in part (a).
