Design and Analysis of Algorithms
Recurrence Analysis
Dr. Lê Nguyên Khôi
The VNU University of Engineering and Technology
Contents
Recursive algorithms
Recurrence analysis:
Mathematical method
Substitution method
Recursion-tree method
Master theorem
Design and Analysis of Algorithms 1
Merge Sort – Pseudocode
MergeSort
1 if return
2 MergeSort
3 MergeSort
4 Merge
Subroutine: Merge
Merge the 2 sorted list
Time to merge a total of elements
(linear time)
Design and Analysis of Algorithms 2
Merge Sort – Analysis
MergeSort
0 MergeSort
1 if return
2 MergeSort
3 MergeSort
4 Merge
Line 2 and 3 should be ,
but it turn out not to matter asymptotically
Design and Analysis of Algorithms 3
Merge Sort – Recurrence Analysis
We shall usually omit stating the base case
when for sufficiently small , but only when it
has no effect on the asymptotic solution to the
recurrence
Solve , with constant
Design and Analysis of Algorithms 4
Merge Sort – Recurrence Analysis
Solve , with constant
Design and Analysis of Algorithms 5
Substitution Method
The most general method:
1. Guess the form of the solution
2. Verify by induction
3. Solve for constants
Example:
Assume that
Guess (prove - and - separately)
Assume that for
Prove by induction
Design and Analysis of Algorithms 6
Substitution Method – Example
Whenever
for example, if and
Design and Analysis of Algorithms 7
Substitution Method – Example
We must also handle the initial
conditions, that is, ground the induction
with base cases
Base case: for all ,
where is a suitable constant
For , we have , if
we pick big enough
This bound is not tight!
Design and Analysis of Algorithms 8
A Tighter Upper Bound?
We shall prove that
Assume that for :
wrong as we must prove the I.H.
for no choice of
Design and Analysis of Algorithms 9
A Tighter Upper Bound?
Idea: Strengthen the inductive hypothesis
By subtracting a low-order term
I.H.: for
if
Pick big enough to handle the initial conditions
Design and Analysis of Algorithms 10
Substitution Method – Exercise
Find the solution for following recurrence:
(ex. 4.3-1 p.87)
(ex. 4.3-2 p.87)
(ex. 4.3-3 p.87)
Design and Analysis of Algorithms 11
Recursion-Tree Method
A recursion tree models the costs (time)
of a recursive execution of an algorithm
The recursion-tree method can be
unreliable
The recursion-tree method promotes
intuition
The recursion tree method is good for
generating guesses for the substitution
method.
Design and Analysis of Algorithms 12
Recursion-Tree Method
Example: p.38
More details: section 4.4 p.88-93
Solve:
Design and Analysis of Algorithms 13
Master Theorem
The master theorem applies to recurrences of
form
where , , and is asymptotically
positive
Example MergeSort:
where , ,
therefore:
Design and Analysis of Algorithms 14
Master Theorem
Idea: compare the growth rate of
and to determine
grows slower than
grows at similar rate as
grows faster than
Design and Analysis of Algorithms 15
Master Theorem
Consider the special case, where :
Use mathematical method
Design and Analysis of Algorithms 16
Master Theorem
Design and Analysis of Algorithms 17
Master Theorem
Case , compare the growth rate of
and
1. grows slower than
2. grows at similar rate as
3. grows faster than
Design and Analysis of Algorithms 18
Master Theorem – slower
Compare with :
1. for constant
slower than by the rate of
therefore:
Design and Analysis of Algorithms 19
Master Theorem – similar
Compare with :
2.
similar as
therefore:
Design and Analysis of Algorithms 20
Master Theorem – faster
Compare with :
3. for constant
faster than by the rate of
and satisfy for
and all sufficient large
therefore:
Design and Analysis of Algorithms 21
Master Theorem
Given 2 constants , , and
Asymptotic of is:
1. If for constant
2. If
3. If for constant
and satisfy for
Design and Analysis of Algorithms 22
Master Theorem – Exercise
Design and Analysis of Algorithms 23
Master Theorem – Exercise
Case 1:
for
Design and Analysis of Algorithms 24
Master Theorem – Exercise
Case 2:
Design and Analysis of Algorithms 25
Master Theorem – Exercise
Case 3:
for
and for
for
Design and Analysis of Algorithms 26
Master Theorem – Exercise
Master method does not apply
for
for
for
for
Design and Analysis of Algorithms 27
Master Theorem – Exercise
Case 1:
Case 2:
Case 3:
Case 3:
Design and Analysis of Algorithms 28
Master Theorem – Exercise
Case 1:
Case 2:
Case 3:
Master theorem does not apply
Design and Analysis of Algorithms 29
Problems 4-1 p.107
Design and Analysis of Algorithms 30
Problems 4-3 p.108
Design and Analysis of Algorithms 31
