RECURRENCE RELATIONS

Recurrence relations define a sequence by giving the nth value in terms of certain of its predecessors. In order for a recurrence relation to define a sequence, start-up values defined as initial conditions must be given. Let’s consider the Fibonacci sequence as a recurrence relation:

fn = fn –1 + fn – 2, and initial conditions f1 = 1 and f2 = 2. There are recursive algorithms that use recurrence relation to compute different values. The following computes the amount of money at the end of n years assuming an initial amount of $2000 and an interest rate of 15 percent compounded annually. The input n is the number of years and the output is the amount of money at the end of n years.

1. procedure compound_interest(n)

2. if n = 0 then

3. return(2000)

4. return(1.15 * compound_interest(n – 1))

5. end compound_interest

Ackerman’s function A(m, n)is a recurrence relation theory that can be used in the time complexity of certain algorithms. It is defined by the recurrecnce relation:

A(m, 0) = A(m – 1, 1), m ≥ 1

A(m, n) = A(m – 1, A(m, n – 1)), m ≥ 1, n ≥ 1

and initial conditions A(0, n) = n + 1, n ≥ 0

To solve a recurrence relation involving the sequence a0, a1, … is to find an explicit formula for the general term an. Iteration is a method used to solve recurrence relations. To do so, one must use the recurrence relation to write the nth term in terms of certain of its predecessors. Then successively use the recurrence relation to replace each of the resulting terms by certain of their predecessors. Continue until an explicit formula is obtained. Recurrences relations can also be solved using a special method of linear homogeneous recurrence relations with constant coefficients.

While analyzing algorithms, it is important to understand how they work and how fast they work.

Selection sort algorithms select the largest element, place it last, and then recursively sort the remaining sequence. They require Θ(n²) time complexity. Binary search algorithms examine the middle item in the sequence. If the middle item is the desired item, binary search terminates. Otherwise, binary search compares the middle item with the desired item. If the desired item is less than the middle item, binary search recursively searches in left half of the sequence. If the desired item is greater than the middle item, binary search recursively searches in the right half of the sequence. The input must be sorted. Merge sort algorithms first divide rthe input into two nearly equal parts. They then recursively sort each half and merge the halves to produce sorted output.

APPLICATIONS

Recurrence relations can be used to solve the big-Oh running time of recursive functions

URL: www.cs.duke.edu

Recurrence relations can be used to solve Tridiagonal Vectors

URL: www.ifa.au.edu

QUESTIONS

1. What are the four characteristics of recurrence relations?

2. What are the two classes of recurrence relations that are always solvable?