Master Theorem

Since I have started tutoring college level computer science I have had to relearn a lot of things that I haven’t used since college (both undergrad and masters). One of them is the Master’s Theorem that is used to analyze the running time for divide-and-conquer algorithms.

Every time I look at these I have to take a minute to remind myself how to determine the run times. So, this post is to handle just that.

First, the general form of the equations:

T(n) = aT(\frac{n}{b}) + f(n)

This has two parts. The first aT(\frac{n}{b}) is the sub problem where the algorithm does the divide-and-conquer. The second part f(n) shows the time it takes to recreate the problem.

There are 3 cases to determine the running time of this algorithm. Each of the is determined by the time it takes to run each part.

Determine the “cost” of each part of the equation:
To determine the sub problem speed you need to solve log_b a.
To determine the recreation you need to solve based on ‘c’ which is different for each case.

Case 1: f(n) = O(n^c)
Case 2: f(n) = O(n^c log^k n)
Case 3: f(n) = \Omega(n^c)

Case 1: When the work to combine the problem is dwarfed by the sub problem.

aT(\frac{n}{b}) > f(n)

Case 2: When the work to combine the problem is comparable to the sub problem.

aT(\frac{n}{b}) \approx f(n)

Case 3: When the work to combine the problem dominates the sub problem

aT(\frac{n}{b}) < f(n)

To start I am going to work through a single instance of each (from wikipedia) and then give multiple examples of each.

Case 1 Example:
T(n) = 8T(\frac{n}{2}) + 1000n^2
First, we need to determine the variables a, b, and c from f(n).
Here, a = 8 and b = 2.
For c, f(n) = 1000n^2. Since we know f(n) = O(n^c). So we get c=2.

For case 1 we need to have log_b a > c
Doing the math log_2 8= 3 which is greater than 2 from c. This confirms we are in case 1.
Using the formula T(n) = O(n^c) we get O(n^3)

Case 2 Example:
T(n) = 2T(\frac{n}{2}) + 10n
First, we need to determine the variables a, b, and c from f(n).
Here, a = 2 and b = 2.
For c, f(n) = 10n. Since we know f(n) = O(n^c log^k n). So we get c=1.

For case 2 we need to have log_b a \approx c
Doing the math log_2 2= 1 which is the same as 1 from c. This confirms we are in case 2.
Using the formula T(n) = O( n^c log^k n ) we get O(n log n)

Case 3 Example:
T(n) = 2T(\frac{n}{2}) + n^2
First, we need to determine the variables a, b, and c from f(n).
Here, a = 2 and b = 2.
For c, f(n) = n^2. Since we know f(n) = O(f(n)). So we get c=2

For case 3 we need to have log_b a < c
Doing the math log_2 2= 1 which is the same as 2 from c. This confirms we are in case 3.
Using the formula T(n) = O( f(n) ) we get O(n^2)

Samples:

Now, I am going to bang through a few examples of each case. Case 1 and 3 are pretty straight forward but we start getting some interesting cases in 2.

Each of these will be broken into 4 sections. The first column will be the formula. The second column will be the results of log_b a. The third column will be the value of c. The last column will be the notation.

These were pulled from Abdul Bari’s YouTube channel.

Case 1 Samples:
T(n) = 2T(\frac{n}{2}) + 1 -> log_b a = 1 -> c=0 -> O(n^1)
T(n) = 4T(\frac{n}{2}) + 1 -> log_b a = 1 -> c=0 -> O(n^2)
T(n) = 4T(\frac{n}{2}) + n -> log_b a = 2 -> c=1 -> O(n^2)
T(n) = 8T(\frac{n}{2}) + n^2 -> log_b a = 3 -> c=2 -> O(n^3)
T(n) = 16T(\frac{n}{2}) + n^2 -> log_b a = 4 -> c=2 -> O(n^4)

Case 3 Samples:
T(n) = T(\frac{n}{2}) + n -> log_b a = 0 -> c=1 -> O(n)
T(n) = 2T(\frac{n}{2}) + n^2 -> log_b a = 1 -> c=2 -> O(n^2)
T(n) = 2T(\frac{n}{2}) + n^2 log n -> log_b a = 1 -> c=2 -> O(n^2 log n)
T(n) = 4T(\frac{n}{2}) + n^3 log n -> log_b a = 2 -> c=3 -> O(n^3 log n)
T(n) = 2T(\frac{n}{2}) + \frac{n^2}{log n} -> log_b a = 1 -> c=2 -> O(n^2)

Case 2 Samples:
Remember, you are multiplying f(n) times log n.
T(n) = T(\frac{n}{2}) + 1 -> log_b a = 0 -> c=0 -> O(log n)
T(n) = 2T(\frac{n}{2}) + n -> log_b a = 1 -> c=1 -> O(n log n)
T(n) = 2T(\frac{n}{2}) + n log n -> log_b a = 1 -> c=1 -> O(n log^2 n)
T(n) = 4T(\frac{n}{2}) + n^2 -> log_b a = 2 -> c=2 -> O(n^2 log n)
T(n) = 4T(\frac{n}{2}) + (n log n)^2 -> log_b a = 2 -> c=2 -> O(n^2 log^3 n)
T(n) = 2T(\frac{n}{2}) + \frac{n}{log n} -> log_b a = 1 -> c=1 -> O(n log log n)
T(n) = 2T(\frac{n}{2}) + \frac{n}{log^2 n} -> log_b a = 1 -> c=1 -> O(n)

Conclusion:

I hope this helps anyone that is struggling through this stuff. After writing all this down with pen and paper it cleared it up for me.