COMP20007 Design of Algorithms
Master Theorem
Lars Kulik Lecture 10 Semester 1, 2021
1
Divide and Conquer
We earlier studied recursion as a powerful problem solving technique.
The divide-and-conquer strategy tries to make the most of this:
1. Divide the given problem instance into smaller instances.
2. Solve the smaller instances recursively.
3. Combine the smaller solutions to solve the original instance.
This works best when the smaller instances can be made to be of equal size.
2
Split-Solve-and-Join Approach
problem of size n
sub-problem 1 of size n/2
sub-problem 2 of size n/2
a solution to sub-problem 1
a solution to sub-problem 2
a solution to the original problem
3
Divide-and-Conquer Algorithms
You have seen:
• Tree traversal
• Closest pair You will learn later:
• Mergesort • Quicksort
4
Divide-and-Conquer Recurrences
What is the time required to solve a problem of size n by divide-and-conquer?
For the general case, assume we split the problem into b instances (each of size n/b), of which a need to be solved:
T(n) = aT(n/b) + f (n)
where f (n) expresses the time spent on dividing a problem into b
sub-problems and combining the a results.
(A very common case is T (n) = 2T (n/2) + n.) How do we find closed forms for these recurrences?
5
The Master Theorem
(A proof is in Levitin’s Appendix B.)
For integer constants a ≥ 1 and b > 1, and function f with
f (n) ∈ Θ(nd ), d ≥ 0, the recurrence
T(n) = aT(n/b) + f (n)
(with T(1) = c) has solutions, and
Θ ( n d ) i f a < b d T(n)= Θ(ndlogn) ifa=bd Θ(nlogb a) if a > bd
Note that we also allow a to be greater than b.
6
Master Theorem: Example 1
T (n) = 2T (n/2) + n
a = 2, b = 2, d = 1
✎
1×n 2×n/2 4×n/4 .
(log2 n times)
7
Master Theorem: Example 2
T (n) = 4T (n/4) + n a = 4, b = 4, d = 1
✎
8
Master Theorem: Example 3
T (n) = T (n/2) + n
a = 1, b = 2, d = 1 n
n/2 n/4 n/8 .
9
Master Theorem: Example 4
T(n) = 2T(n/2) + n2 a = 2, b = 2, d = 2
Here a < bd and we simply get nd.
10