Masters Theorem: A deeper dive into algorithms.

Master’s technique is a quite helpful procedure for solving recurrence equations because it directly gives us the cost of an algorithm with the help of the type of a recurrence equation and it is applied when the recurrence equation is in the form of:

T(n) = a T(n/b) + f (n),

where a ³ 1, b > 1, and f is asymptotically positive function.

An asymptotically positive function means that for a sufficiently large value of n, we have f(n) > 0.

In the application to the analysis of a recursive algorithm, the constants and function are defined as:
• n is the size of the problem.
• a is the number of subproblems (recursion).
• n/b is the size of each subproblem.
• f (n) is the cost of the labor done except the recursive calls, which includes the cost of dividing the question and the cost of merging the solutions to the subproblems.

Idea Behind the Master’s Method

The idea behind the Master’s method is to compare

with the function f(n)f(n) and the entire Master’s Theorem is based on this comparison. In layman’s terms, we are basically finding out which among

and f(n)f(n) is dictating another.

We can understand this by the following 3 cases:

Each of the above conditions can be understood as:

Examples

Example 1:

Example 2:

Example 3:

Application to common algorithms

Master Theorem Limitations

The master theorem cannot be used if:

• T(n) is not monotone. e.g., T(n) = sin n
• f(n) is not a polynomial. e.g., f(n) = 2n
• a is not a constant. e.g., a = 2n
• a < 1

Extended Master’s theorem

Divide and conquer is an algorithm that works on the concept based on recursively splitting problems into multiple sub-problems of similar types that can be solved easily.

Example

function recursive(input x size n)

if(n < k)

Divide the input into m subproblems of size n/p.

and call f recursively of each subproblem

else

Solve x and return

Combine the results of all subproblems and return the solution.

Masters Theorem for divide and conquer is an analysis theorem that is used to determine a big-0 value for recursive relation algorithms. It is used to find the time required by the algorithm and represent it in asymptotic notation form.

Example of runtime value of the problem in the above example −

For most of the recursive algorithm, we will be able to find the Time complexity For the algorithm using the master’s theorem, but there are some cases master’s theorem may not be applicable. These are the cases in which the master’s theorem is not applicable. When the problem T(n) is not monotone, for example, T(n) = sin n. Problem function f(n) is not a polynomial.

As the master theorem to find time complexity is not hot efficient in these cases, an advanced master theorem for recursive recurrence was designed. It is designed to handle recurrence problem of the form −

Where n is the size of the question.

a = number of subproblems in recursion, a > 0

n/b = size of each subproblem

Solution:

Using the advanced master algorithm, we will calculate the complexity of some algorithms −

Binary search − t(n) = θ(logn)

Merge sort − T(n) = θ(nlogn)