Design and Analysis of Algorithm
Course Code :
Lecture 2
Recurrences, Solution of Recurrences by substitution,
Recursion Tree and Master Method
Dr. Huma Qayyum
Department of Software Engineering
[email protected] • Recursion is generally expressed in terms of
recurrences. In other words, when an
algorithm calls to itself, we can often describe
its running time by a recurrence equation
which describes the overall running time of a
problem of size n in terms of the running time
on smaller inputs.
What is a recurrence relation?
• A recurrence relation, T(n), is a recursive function of integer variable n.
• Like all recursive functions, it has both recursive case and base case.
• Example:
• The portion of the definition that does not contain T is called the base case of
the recurrence relation; the portion that contains T is called the recurrent or
recursive case.
• Recurrence relations are useful for expressing the running times (i.e., the
number of basic operations executed) of recursive algorithms
Forming Recurrence Relations
• Example : Write the recurrence relation for the following method.
public int g(int n) {
if (n == 1)
return 2;
else
return 3 * g(n / 2) + g( n / 2) + 5;
}
• The base case is reached when n == 1. The method performs one
comparison and one return statement. Therefore, T(1), is constant c.
• When n > 1, the method performs TWO recursive calls, each with the
parameter n / 2, and some constant # of basic operations.
• Hence, the recurrence relation is:
Solving Recurrence Relations
• To solve a recurrence relation T(n) we need to derive a form of
T(n) that is not a recurrence relation. Such a form is called a
closed form of the recurrence relation.
• Three Common methods used to solve recurrence relations that
represent the running time of recursive methods:
Substitution method
Recursion tree method
Master method
Solving Recurrence Relations - Iteration method
• Steps:
Expand the recurrence
Express the expansion as a summation by plugging the recurrence
back into itself until you see a pattern.
Evaluate the summation
• In evaluating the summation one or more of the following summation
formulae may be used:
• Arithmetic series:
•Special Cases of Geometric Series:
Geometric Series:
Solving Recurrence Relations - Iteration method
Harmonic Series:
Others:
Analysis Of Recursive Binary Search
public int binarySearch (int target, int[] array,
int low, int high) {
if (low > high)
return -1;
else {
int middle = (low + high)/2;
if (array[middle] == target)
return middle;
else if(array[middle] < target)
return binarySearch(target, array, middle + 1, high);
else
return binarySearch(target, array, low, middle - 1);
}
}
• The recurrence relation for the running time of the method is:
T(1) = a if n = 1 (one element array)
T(n) = T(n / 2) + b if n > 1
Analysis Of Recursive Binary Search
Expanding:
T(n) = T(n / 2) + b
= [T(n / 4) + b] + b = T (n / 22) + 2b
= [T(n / 8) + b] + 2b = T(n / 23) + 3b
= ……..
= T( n / 2k) + kb
When n / 2k = 1 n = 2k k = log2 n, we have:
T(n) = T(1) + b log2 n
= a + b log2 n
Therefore, Recursive Binary Search is O(log n)
Tower of Hanoi
• Explicit Pattern
• Number of Disks Number of Moves
1 1
2 3
3 7
4 15
5 31
• Powers of two help reveal the pattern:
• Number of Disks (n) Number of Moves
1 2^1 - 1 = 2 - 1 = 1
2 2^2 - 1 = 4 - 1 = 3
3 2^3 - 1 = 8 - 1 = 7
4 2^4 - 1 = 16 - 1 = 15
5 2^5 - 1 = 32 - 1 = 31
Analysis Of Recursive Towers of Hanoi Algorithm
public static void hanoi(int n, char BEG, char AUX, char END){
if (n == 1)
System.out.println(from + " --------> " + to);
else{
hanoi(n - 1, BEG, END, AUX);
System.out.println(from + " --------> " + to);
hanoi(n - 1, END, AUX, BEG);
}
}
• The recurrence relation for the running time of the method
hanoi is:
T(n) = a if n = 1
T(n) = 2T(n - 1) + b if n > 1
Analysis Of Recursive Towers of Hanoi Algorithm
Expanding:
T(n) = 2T(n – 1) + b
= 2[2T(n – 2) + b] + b = 22 T(n – 2) + 2b + b
= 22 [2T(n – 3) + b] + 2b + b = 23 T(n – 3) + 22b + 2b + b
= 23 [2T(n – 4) + b] + 22b + 2b + b = 24 T(n – 4) + 23 b + 22b + 21b + 20b
= ……
= 2k T(n – k) + b[2k- 1 + 2k– 2 + . . . 21 + 20]
When k = n – 1, we have:
Therefore, The method hanoi is O(2n)
The Recursion Tree
• Another way of characterizing recurrence equations is to use the
recursion tree method. Like the iterative substitution method, this
technique uses repeated substitution to solve a recurrence
equation, but it differs from the iterative substitution method in that,
rather than being an algebraic approach, it is a visual approach.
The Recursion Tree
• A recursion tree models the costs (time) of a recursive execution of
an algorithm.
• •
• The recursion tree method is good for generating guesses for the
substitution method.
• The recursion-tree method promotes intuition
Recursion Tree Method
Example:
Solve the following recurrence using recurrence tree method
(1) if n 1
T ( n)
n
3.T ( ) (n 2 ) if otherwise
4
Solution: The above recurrence can be written in the form
1 if n 1
T ( n)
n
3.T ( ) cn 2 if otherwise
4
Assumption: We assume that n is exact power of 4.
The recurrence tree is given in the next slide
Recursion Tree Method
c.n2
T(n) = 3.T(n/4)+c.n2
T(n/4) T(n/4) T(n/4)
c.n2
c.(n/4)2 c.(n/4)2 c.(n/4)2
T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16) T(n/16)
Recursion Tree Method
c.n2 c.n2
c.(n/4)2 c.(n/4)2 c.(n/4)2 (3/16).c.n2
2
c(n/16)2 c(n/16)2 c(n/16)2 c(n/16)2 c(n/16)2 c(n/16)2 c(n/16)2 c(n/16)2 c(n/16)
(3/16)2.c.n2
T(n/4k) T(n/4k) T(n/4k) T(n/4k) T(n/4k) T(n/4k) T(n/4k) T(n/4k)
Recursion Tree Method
c.n2 c.n2
Suppose n = 4k
Log4n
c.(n/4)2 c.(n/4)2 c.(n/4)2 (3/16).c.n2
2 2 2
c(n/16)2 c(n/16)2 c(n/16) c(n/16)2 c(n/16)2 c(n/16) c(n/16) c(n/16) c(n/16)
2 2
(3/16)2.c.n2
(3/42)k-1 cn2
T(n/4k) T(n/4k) T(n/4k) T(n/4k) T(n/4k) T(n/4k) T(n/4k) T(n/4k)
T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) (nlog43)
Recursion Tree Method
• Now the total computation cost would be
logn4
T ( n) 3 cost at Levels above child level
log3 4 3 0 3 1 3 k 1 2
T ( n) ( n ) ( 2 ) ( 2 ) ( 2 ) cn
4 4 4
Recursion Tree Method
Now total computational cost can be calculated as
log3 4 3 0 3 1 3 k 1 2
T ( n) ( n ) ( 2 ) ( 2 ) ( 2 ) cn
4 4 4
Where 4 h n h log4 n
log3 4 3 0 3 1 2
T ( n ) ( n ) ( 2 ) ( 2 ) cn
4 4
log3 4 1 log3 4 16 2
T ( n ) ( n )( )cn (n
2
) cn
3 13
1 ( )
16
Hence T (n) (n 2 )
