Master Theorem and Examples

When we analyze the loop we find many times it calls in the recursion, and many of the algorithm are recursive in nature. On the analysis of the algorithm we find out about the recurrence relation for the time complexity of the algorithm.

For example we take the case in the merge sort where we have to sort the given array and to sort the given array firstly we divide this array into two equal parts and each part is divided into two equal parts and this process will keep on going till we reach the simplest structure. When the division has taken place then the sorting of the elements will start from that simplest level. This dividing of the problem requires and solving of the simpler sub problem makes it recursive in nature.

Master Method or Master Theorem

Masters method is used to determine the time taken by the algorithm to complete its function in the terms of the asymptotic notations.

Beside the master method there are many method to solve the recursion relation like substitution method, the substitution method is little bit of time taking due to longer mathematics and can solve many equations. But Master Method or the Master Theorem is faster but to solve the master method the equation should be specific unlike the substitution method which can be used to solve any recursive relation.

Master method is a much more direct way to get to the solution faster and for the type of the recurrence that can be applied by the masters method, it has to be some particular form or has to fulfil the following criteria.

Master method is one of the fastest method in recurrence relation to determine the time and the cost of the running algorithm.

This method can also be termed as the divide and conquer technique, where the problem is divided into several sub parts.

In this algorithm the problem is divided into ‘a’ sub-parts of the main problem. And the size of the each is kept as (n/b) and the work that is required for the algorithm to complete is f(n).

So combining our above statement the equation is, T (n) = aT(n/b) + f(n).

Where the size of the input is getting reduced by the division and turns into simpler sub problem to solve.
We also have to calculate the cost of the sub problem and then you will combine the entire sub problem to get the cost of the complete problem.

To solve the problem with the master theorem you have to see whether the problem is being simplified on the division.

The size of the sub problem will always be the same.

Rules of Master Method

There are three set of rules that can be helped to solve master problem.

We have to identify the ‘a’ and then identify the ’b’ in the equation and then determine the theta when the theta is determined we have to use the epsilon to match the theta with our function.

If all goes well the case will match up in the above case it matches with the rule one.

Sometimes the function of the calculation will result in the same rule and their will no use of the epsilon to match the functions.

Master Method and Recursion Tree

Master method can resemble with the recurrence tree method. You can easily expand the tree and find the resemblance of the tree and the master method. IN recurrence tree we have to calculate the work done at each level. So, if the work done by the leave nodes is much more than the result will become the work done at leaves. But, when the work done by the leaves and root are same then the height of the tree is multiplied with the work done at each level of the tree. If the work done at the root is more than the result of the work done at the node becomes our result.
The same approach can be seen in the master method. If we expand the original equation of the master method and draw a recurrence tree we will find that the relationship between the work done at various level and height of the tree matching to our equation.

Leave a Comment