CS 3343/3341, Recurrences: Master Theorem

CS 3343/3341
Analysis of Algorithms

Recurrences
Master Theorem

Introduction: Here is your text's statement of the theorem and a brief overview description:

Click picture or here for full size picture.

The paragraph at the end above describes the "Cookbook" aspect of this theorem. It amounts to a simple sequence of steps. [Illustrated here for the recurrence: T(n) = 4 T(n/2) + n²]:

Determine the magic numbers a and b. [Here a = 4 and b = 2.] Calculate log_b(a). [Here log₂(4) = 2. In general, to calculate log_b(a) = x, remember that this means b^x = a. You can also use log_b(a) = log₁₀(a) / log₁₀(b).] Focus on the function n^log_b(a). [Here this is n².] Compare the function in iii above to the function f(n), with the comparision as powers of n. We are comparing the exponents of n. [Here they are equal, both n².] Now there are three cases: Case > : If n^log_b(a) > f(n), then T(n) = Θ(n^log_b(a) ). [This is not true in our example, but if f(n) were equal to n in our example, then we would have T(n) = Θ(n²).] Case = : If n^log_b(a) = f(n), then T(n) = Θ(n^log_b(a) log₂(n)). [This is the situation in the example we are using, so T(n) = Θ(n² log₂(n)).] Case < : If n^log_b(a) < f(n), then T(n) = Θ(f(n)). [This is not true in our example, but if f(n) were equal to n³ in our example, then we would have T(n) = Θ(f(n)) = Θ(n³).] [In our example above, if f(n) were equal to n² log(n), then it might seem like Case 3 would apply, since f(n) is larger, but for case 3 to apply, f(n) must be larger as a power of n. So here the Master Method would not work at all.]

Determine the magic numbers a and b. [Here a = 4 and b = 2.]
Calculate log_b(a). [Here log₂(4) = 2. In general, to calculate log_b(a) = x, remember that this means b^x = a. You can also use log_b(a) = log₁₀(a) / log₁₀(b).]
Focus on the function n^log_b(a). [Here this is n².]
Compare the function in iii above to the function f(n), with the comparision as powers of n. We are comparing the exponents of n. [Here they are equal, both n².]
Now there are three cases:
1. Case > : If n^log_b(a) > f(n), then T(n) = Θ(n^log_b(a) ). [This is not true in our example, but if f(n) were equal to n in our example, then we would have T(n) = Θ(n²).]
2. Case = : If n^log_b(a) = f(n), then T(n) = Θ(n^log_b(a) log₂(n)). [This is the situation in the example we are using, so T(n) = Θ(n² log₂(n)).]
3. Case < : If n^log_b(a) < f(n), then T(n) = Θ(f(n)). [This is not true in our example, but if f(n) were equal to n³ in our example, then we would have T(n) = Θ(f(n)) = Θ(n³).]
[In our example above, if f(n) were equal to n² log(n), then it might seem like Case 3 would apply, since f(n) is larger, but for case 3 to apply, f(n) must be larger as a power of n. So here the Master Method would not work at all.]

Here are some specific examples. The first three give the example in the description above, along with its two variants. The next two examples are regular matrix multiplication and Strassen's version: matrix multiplication. The two examples after that are regular integer multiplication, and the divide and conquer version: Multiply in Θ(n^1.585). For the last example, where the Master Method fails, see the discussion in your text, at the bottom of page 95 and on to the top of page 96.

Recurreces, solution by Master Method, Examples
Recurrence	a	b	log_b(a)	n^log_b(a)	f(n)	Case	Behavior
T(n) = 4 T(n / 2) + n²	4	2	log₂(4) = 2	n²	n²	2	Θ(n² log₂(n))
T(n) = 4 T(n / 2) + n	4	2	log₂(4) = 2	n²	n	1	Θ(n²)
T(n) = 4 T(n / 2) + n³	4	2	log₂(4) = 2	n²	n³	3	Θ(n³)
T(n) = 8 T(n / 2) + Θ(n²)	8	2	log₂(8) = 3	n³	n²	1	Θ(n³)
T(n) = 7 T(n / 2) + Θ(n²)	7	2	log₂(7) = 2.807	n^2.807	n²	1	Θ(n^2.81)
T(n) = 4 T(n / 2) + Θ(n)	4	2	log₂(4) = 2	n²	n	1	Θ(n²)
T(n) = 3 T(n / 2) + Θ(n)	3	2	log₂(3) = 1.585	n^1.585	n	1	Θ(n^1.585)
T(n) = 2 T(n / 2) + n*log(n)	2	2	log₂(2) = 1	n¹	n*log(n)	none	Master fails

Revision date: 2012-02-18. (Please use ISO 8601, the International Standard Date and Time Notation.)