Dr. Huma Qayyum Department of Software Engineering Huma - Ayub@uettaxila - Edu.pk

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
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)

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)

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)
• 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 
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 )

Dr. Huma Qayyum Department of Software Engineering Huma - Ayub@uettaxila - Edu.pk

Uploaded by

Document Informationclick to expand document information The recurrence tree method provides useful intuition for solving recurrences. By modeling the recursive calls as a tree, we can visualize the overall cost and derive closed form solutions.

Document Informationclick to expand document information

Copyright:

Available Formats

Dr. Huma Qayyum Department of Software Engineering Huma - Ayub@uettaxila - Edu.pk

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Dr. Huma Qayyum Department of Software Engineering Huma - Ayub@uettaxila - Edu.pk

Uploaded by

Copyright:

Available Formats

Design and Analysis of Algorithm

Dr. Huma Qayyum

• A recurrence relation, T(n), is a recursive function of integer variable n.

public int g(int n) {

• To solve a recurrence relation T(n) we need to derive a form of

• Three Common methods used to solve recurrence relations that

When n / 2k = 1  n = 2k  k = log2 n, we have:

T(n) = T(1) + b log2 n

Therefore, Recursive Binary Search is O(log n)

• Number of Disks (n) Number of Moves

Therefore, The method hanoi is O(2n)

• A recursion tree models the costs (time) of a recursive execution of

T(n/4) T(n/4) T(n/4)

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)

c.(n/4)2 c.(n/4)2 c.(n/4)2 (3/16).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)

c.(n/4)2 c.(n/4)2 c.(n/4)2 (3/16).c.n2

You might also like