580 CHAPTER 9 Recurrence Relations
- Solve these recurrences using back substitution. Verify the solutions are correct by
induction.
(1a,/2+4 fork>0, n=2k
(a) an/=4 for n = 1
(b) (5an/5+7 112 fork>0, forn= I n=^5 k
(C) an = (c= a/3+5 fork>0, n=^3 k
for n = 1(d) an (17an/4+3 fork>0,n=4kfor n = 1
- Find two sorted lists of length five that require nine comparisons to merge into one
sorted list of size 10. - Write a divide-and-conquer algorithm to find the largest and smallest element in a set
with 2 k elements for some k > 0. Determine the complexity of your algorithm. - If n > 0, show that
(Hint: Consider the cases n odd and n even separately.)- Determine the difference in performance between the methods described for calculat-
ing the Fibonacci numbers:
(a) Directly implement the relation F, = Fn-j + F,- 2.
(b) Define a recursive function that has Fn-1 and Fn-2 passed as parameters when
calculating Fn.
(c) Use the relations
F2n = (F. + 2Fn- 1 ) -Fn
F2n_1 = F2 + Ff2
F2n-2 = (2Fn - F,- 1 ) • F.-1
to generate pairs of Fibonacci numbers.Chapter Review
A function often can be defined either recursively or iteratively. Programs also can be
written in either way. This chapter is a brief introduction to the mathematics that can be
used to compute the complexity of some recursive algorithms. Recursive algorithms can
have their complexity described by recurrence relations. The problem we deal with here is
to find a closed form for these recurrence relations. A recurrence relation with a value at n
that depends on the value of the function at n - 1 is called a first-order recurrence relation.
The method of back substitution is used to solve such recurrences. A recursive function
with a value at n that depends on the value of the function at both n - 1 and n - 2 is called
a second-order recurrence relation. The method of complementary equations is used to
solve such recurrences. Finally, divide-and-conquer recurrence relations determine the