Master theorem

Solve T(n) = aT(n/b) + f(n).

Master theorem

The master theorem solves recurrences of the form T(n) = aT(n/b) + f(n). Here a is the subproblem count, b the split ratio.

It gives three cases; each yields a different complexity class and a quick solution.

The master theorem lets us quickly compute the complexity of divide and conquer algorithms.

Three cases

Case 1: if f(n) is small, T(n) = Θ(n^log_b a). Case 2: if f(n) = Θ(n^log_b a), then T(n) = Θ(n^log_b a * log n). Case 3: if f(n) is large, T(n) = Θ(f(n)).

Example: T(n) = 2T(n/2) + n, log_2 2 = 1, case 2, T(n) = Θ(n log n).

These cases quickly yield the Θ(n log n) result for algorithms like merge sort.

Exercise Compute master

Write master_log_b_a(a, b). Return log_b a. Print 1.0 with print(master_log_b_a(2, 2)).

Show example solution

def master_log_b_a(a, b):
    # Compute log_b a
    import math
    return math.log(a, b)
print(master_log_b_a(2, 2))

Test yourself

Master theorem: match the terms

a

Subproblem count
b

Split ratio
f(n)

Combine
Θ

Complexity
What solves T(n) = 2T(n/2) + n?
- Θ(n^2)
- Θ(2^n)
- Θ(log n)
- Θ(n log n)
Show answer

Θ(n log n) — Θ(n log n).

Master formula

T(n) = aT(n/____) + f(n)

Show answer

T(n) = aT(n/b) + f(n)

Next lesson: Summary - Divide and conquer

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies