CmSc250 Intro to Algorithms
Solving Recurrence Relations
1. Definition: A recurrence relation for the sequence {an} is an equation that expresses an in terms of one or more of the previous terms of the sequence, namely a0, a1, , a n-1, for all integers n, with n ³ n0, where n0 is a nonnegative integer.
n0 is the index of the first term where the recurrence relation takes effect.
Example: Fibonacci numbers:
1, 1, 2, 3, 5, 8, 11, .
F1 = 1, F2 = 1
Fn = Fn-1 + Fn-2, n =3,4, .
2. Initial condition: specifies the terms that precede the first term where the recurrence relation takes effect.
Example: in the Fibonacci recurrence relation, the initial condition is: F1 = 1, F2 = 1.
3. Application of recurrence relations in algorithm analysis.
For a given algorithm, consider the sequence T(1), T(2), . T(N), where T(N) is the time necessary to process input of size N. If we can find a recurrence relation for that sequence, we may be able to express T(N) in terms of N.
Examples:
Problem 1: Insertion sort
Initial condition: the time to sort an array of 1 element is constant:
T(1) = O(1) = 1
Recurrence relation: The time to sort an array of N elements is equal to the time to sort an array of N-1 elements plus N-1 comparisons.
T(N) = T(N-1) + N-1
Next we perform telescoping: re-writing the recurrence relation for N-1, N-2, , 2
T(N) = T(N-1) + N-1
T(N-1) = T(N-2) + N-2
T(N-2) = T(N-3) + N-3
T(2) = T(1) + 1
Next we sum up the left and the right sides of the equations above:
T(N) + T(N-1) + T(N-2) + T(N-3) + . T(3) + T(2) =
= T(N-1) + T(N-2) + T(N-3) + . T(3) + T(2) + T(1) +
(N-1) + (N-2) + (N-3) + . +3 + 2 + 1
Finally, we cross the equal terms on the opposite sides and simplify the remaining sum on the right side:
T(N) = T(1) + N*(N-1)/2 1 + N*(N - 1)/2
T(N) = 1 + N*(N - 1)/2
Therefore the running time of insertion sort is:
T(N) = O(1 + N*(N - 1)/2) = O(N2)
Problem 2: Binary search in a sorted array
Algorithm Search (E) in array[1..N]:
Compare E with the middle element.
If equal : stop with success
If not equal and N = 1: stop with failure
If E is greater, search E in array[N/2+1 .. N]
Otherwise, search E in array[1 .. N/2]
Initial condition: the time to search in an array of 1 element is constant:
T(1) = O(1) = 1
Recurrence relation: The time to search in an array of N elements is equal to the time to search in an array of N/2 elements plus 1 comparison.
T(N) = T(N/2) + 1
Next we perform telescoping: re-writing the recurrence relation for N/2, N/4, , 2
T(N) = T(N/2) + 1
T(N/2) = T(N/4) + 1
T(N/4) = T(N/8) + 1
T(4) = T(2) + 1
T(2) = T(1) + 1
Next we sum up the left and the right sides of the equations above:
T(N) + T(N/2) + T(N/4) + T(N/8) + +T(2) =
T(N/2) + T(N/4) + T(N/8) + +T(2) + T(1) + (1 + 1 + + 1)
The number of 1s on the right side is LogN
Finally, we cross the equal terms on the opposite sides and simplify the remaining sum on the right side:
T(N) = T(1) + LogN
T(N) = 1 + LogN
Therefore the running time of binary search is:
T(N) = O(LogN)
Problem 3: Reverse a queue
Algorithm Reverse(P):
If queue P is not empty do:
Dequeue(P) ΰ e
Reverse(P)
Enqueue(P,e)
Initial condition: the time to reverse a queue of 1 element is constant:
T(1) = O(1) = 1
Recurrence relation: The time to reverse a queue of N elements is equal to the time to reverse a queue of N-1 elements plus 2 operations (dequeue and enqueue).
Next we perform telescoping: re-writing the recurrence relation for N-1, N-2, , 2
T(N) = T(N-1) + 2
T(N-1) = T(N-2) + 2
T(N-2) = T(N-3) + 2
T(2) = T(1) + 2
Next we sum up the left and the right sides of the equations above:
T(N) + T(N-1) + T(N-2) + T(N-3) + . T(3) + T(2) =
= T(N-1) + T(N-2) + T(N-3) + . T(3) + T(2) + T(1) + 2*(N-1)
Finally, we cross the equal terms on the opposite sides and simplify the remaining sum on the right side:
T(N) = T(1) + 2*(N-1)
T(N) = 1 + 2*(N-1)
Therefore the running time of reversing a queue is:
T(N) = O(1 + 2*(N-1)) = O(N)
Problem 4: Tree traversals
Consider preorder traversal a perfect binary tree
preorder_traversal (root)
Visit root
preorder_traversal(left_subtree)
preorder_traversal (right_subtree)
Let the tree have N nodes, then the right and the left subtree will have roughly N/2 nodes.
T(1) = O(1) = 1
T(N) = 2T(N/2) + 1
2T(N/2) = 4T(N/4) + 2
4T(N/4) = 8T(N/8) + 4
N/4 * T(4) = N/2 * T(2) + N/4
N/2 * T(2) = N T(1) + N/2
Note: How to compute the coefficient in front of T(2) :
We notice that the coefficient is equal to the denominator of the Ts argument.
The argument 2 is equal to N divided by the coefficient C, i.e. 2 = N/C
Therefore C = N/2
After adding all the right sides and all the left sides and crossing the equal terms, we obtain:
T(N) = NT(1) + 1 + 2 + + N/4 + N/2 (1)
We know that 1 + 2 + 22 + + 2p = 2 (p+1) -1
In order to apply the formula, we have to represent N/2 as a power of 2
We know that 2logN = N, therefore N/2 = 2log(N/2)
Thus we get:
1 + 2 + + N/4 + N/2 = 1 + 2 + 22 + + 2log(N/2) = 2log(N/2) + 1 -1 =
= 2*2log(N/2) - 1 = 2*(N/2) - 1
Substituting in (1) we get:
T(N) = N*T(1) + 2*(N/2) 1 = N + N -1 = 2*N 1
Therefore the running time of tree traversal is:
T(N) = O(2*N 1) = O(N)