Masters Method Examples

For Complete YouTube Video: Click Here

In this class, we will try to understand Masters Method Examples.

We have already discussed the concept of masters method in our previous class.

Masters Method Examples

To find the efficiency of a recursive algorithm we have maters method.

The masters method uses the following formula to find the efficiencey of recursive algorithms.

Based on the above table we will find the efficiency of recursive algorithms.

Example 1

From the above example it will fall into 2a option because a = b^k and p > -1.

The efficiency of the algorithm is ɵ(n² log n).

Example 2

From the above example it will fall into 3a option because a < b^k and p >= 0.

The efficiency of the algorithm is ɵ(n² ).

Example 3

From the above example it will fall into 2a option because a = b^k and p > -1.

The efficiency of the algorithm is ɵ(n log² n ).

Example 4

We cannot find the efficiency using the masters method because a should be greater than or equal to 1.

In the above example a is 2ⁿ.

Masters method is not applicable for all the recurrence relations.