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:

This has two parts. The first is the sub problem where the algorithm does the divide-and-conquer. The second part 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 .

To determine the recreation you need to solve based on ‘c’ which is different for each case.

Case 1:

Case 2:

Case 3:

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

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

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

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**:

First, we need to determine the variables a, b, and c from f(n).

Here, a = 8 and b = 2.

For c, . Since we know . So we get c=2.

For case 1 we need to have

Doing the math which is greater than 2 from c. This confirms we are in case 1.

Using the formula we get

**Case 2 Example**:

First, we need to determine the variables a, b, and c from f(n).

Here, a = 2 and b = 2.

For c, . Since we know . So we get c=1.

For case 2 we need to have

Doing the math which is the same as 1 from c. This confirms we are in case 2.

Using the formula we get

**Case 3 Example**:

First, we need to determine the variables a, b, and c from f(n).

Here, a = 2 and b = 2.

For c, . Since we know . So we get c=2

For case 3 we need to have

Doing the math which is the same as 2 from c. This confirms we are in case 3.

Using the formula we get

**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 . 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**:

-> = 1 -> c=0 ->

-> = 1 -> c=0 ->

-> = 2 -> c=1 ->

-> = 3 -> c=2 ->

-> = 4 -> c=2 ->

**Case 3 Samples**:

-> = 0 -> c=1 ->

-> = 1 -> c=2 ->

-> = 1 -> c=2 ->

-> = 2 -> c=3 ->

-> = 1 -> c=2 ->

**Case 2 Samples**:

Remember, you are multiplying f(n) times log n.

-> = 0 -> c=0 ->

-> = 1 -> c=1 ->

-> = 1 -> c=1 ->

-> = 2 -> c=2 ->

-> = 2 -> c=2 ->

-> = 1 -> c=1 ->

-> = 1 -> c=1 ->

## 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.