Master Theorem:
Practice Problems and Solutions
Master Theorem
The Master Theorem applies to recurrences of the following form:
T (n) = aT (n/b) + f (n)
where a ≥ 1 and b > 1 are constants and f (n) is an asymptotically positive function.
There are 3 cases:
1. If f (n) = O(nlogb a− ) for some constant > 0, then T (n) = Θ(nlogb a ).
2. If f (n) = Θ(nlogb a logk n) with1 k ≥ 0, then T (n) = Θ(nlogb a logk+1 n).
3. If f (n) = Ω(nlogb a+ ) with > 0, and f (n) satisfies the regularity condition, then T (n) = Θ(f (n)).
Regularity condition: af (n/b) ≤ cf (n) for some constant c < 1 and all sufficiently large n.
Practice Problems
For each of the following recurrences, give an expression for the runtime T (n) if the recurrence can be
solved with the Master Theorem. Otherwise, indicate that the Master Theorem does not apply.
1. T (n) = 3T (n/2) + n2
2. T (n) = 4T (n/2) + n2
3. T (n) = T (n/2) + 2n
4. T (n) = 2n T (n/2) + nn
5. T (n) = 16T (n/4) + n
6. T (n) = 2T (n/2) + n log n
1 most of the time, k = 0
1
Practice Problems and Solutions
Master Theorem
The Master Theorem applies to recurrences of the following form:
T (n) = aT (n/b) + f (n)
where a ≥ 1 and b > 1 are constants and f (n) is an asymptotically positive function.
There are 3 cases:
1. If f (n) = O(nlogb a− ) for some constant > 0, then T (n) = Θ(nlogb a ).
2. If f (n) = Θ(nlogb a logk n) with1 k ≥ 0, then T (n) = Θ(nlogb a logk+1 n).
3. If f (n) = Ω(nlogb a+ ) with > 0, and f (n) satisfies the regularity condition, then T (n) = Θ(f (n)).
Regularity condition: af (n/b) ≤ cf (n) for some constant c < 1 and all sufficiently large n.
Practice Problems
For each of the following recurrences, give an expression for the runtime T (n) if the recurrence can be
solved with the Master Theorem. Otherwise, indicate that the Master Theorem does not apply.
1. T (n) = 3T (n/2) + n2
2. T (n) = 4T (n/2) + n2
3. T (n) = T (n/2) + 2n
4. T (n) = 2n T (n/2) + nn
5. T (n) = 16T (n/4) + n
6. T (n) = 2T (n/2) + n log n
1 most of the time, k = 0
1
