Master Theorem By : Nikeeta Garrade

MASTER THEOREM

 

The Master Theorem is a tool used to solve recurrence relations that arise in the analysis of divide-and-conquer algorithms. The Master Theorem provides a systematic way of solving recurrence relations of the form:

 

                                               T(n) = aT(n/b) + f(n)

 

1.    where a, b, and f(n) are positive functions and n is the size of the problem. The Master Theorem provides conditions for the solution of the recurrence to be in the form of O(n^k) for some constant k, and it gives a formula for determining the value of k.

 

2.    The advanced version of the Master Theorem provides a more general form of the theorem that can handle recurrence relations that are more complex than the basic form. The advanced version of the Master Theorem can handle recurrences with multiple terms and more complex functions.

 

3.    It is important to note that the Master Theorem is not applicable to all recurrence relations, and it may not always provide an exact solution to a given recurrence. However, it is a useful tool for analysing the time complexity of divide-and-conquer algorithms and provides a good starting point for solving more complex recurrences.

 

    Theory and Cases:

 

 

 

Master Theorem is used to determine running time of algorithms (divide and conquer algorithms) in terms of asymptotic notations.

Consider a problem that is solved using recursion.

 

 

function f (input x size n)

 

if (n < k)

 

solve x directly and return

 

else

 

divide x into a subproblems of size n/b

 

call f recursively to solve each subproblem

 

Combine the results of all sub-problems

 

 

 

The above algorithm divides the problem into a subproblems, each of size n/b and solve them recursively to compute the problem and the extra work done for problem is given by f(n), i.e., the time to create the subproblems and combine their results in the above procedure. So, according to master theorem the runtime of the above algorithm can be expressed as:

 

T(n) = aT(n/b) + f(n) 

 

where n = size of the problem

a = number of subproblems in the recursion and a >= 1

n/b = size of each subproblem

f(n) = θ (n^k. log P to base n) cost of work done outside the recursive calls like dividing into subproblems and cost of combining them to get the solution.

 

Not all recurrence relations can be solved with the use of the master theorem i.e., if

 

·        T(n) is not monotone, ex: T(n) = sin n

 

·        f(n) is not a polynomial, ex: T(n) = 2T(n/2) + 2n

 

 

 

This theorem is an advance version of master theorem that can be used to determine running time of divide and conquer algorithms if the recurrence is of the following form: -

 

 

 

 

 

Where n = size of the problem

a = number of subproblems in the recursion and a >= 1

n/b = size of each subproblem

b > 1, k >= 0 and p is a real number.

 

 

 

 

 

Cases:

 

Case 1: log b a> k, then T(n)= θ (n( log b a)).

 

 

 

Case 2: log b a= k, then the value of T(n) depends upon the value of ‘p’.

 

·        if (p>-1) then T(n)= θ ((nk) (log (p+1) n)).

 

·        if (p= -1) then T(n)= θ ((nk) (log log n)).

 

·        if (p< -1) then T(n)= θ (nk).

 

 

Case 3:  log b a< k, then the value of T(n) depends upon the value of ‘p’. 

 

·        if(p>= 0) then T(n)= θ ((nk) (log p n)).

 

·        if(p< 0) then T(n)= θ (nk).   

 

 

 

 Steps to Solve Master Theorem Examples:

Step 1: Compare the given equation with general Master Theorem equation. Find out the value of a, b, f(n). Equate the value of f(n) with equation n^k.log p n. Find the value of K and P respectively.

 

Step 2: After finding the value of P and K; apply each case to the equation and find out that which one of the cases is finds to be true for the respective given equation.

 

Step 3: As soon as the condition becomes true, you have to stop there, and have to find that, what is the time complexity T(n) for the given condition. Then you have to put all the values of a, b, k, P in that equation. You will get the time complexity of the recurrence relation.

 

 

 

*   Examples on Master Theorem of Increasing Function:

 

 

 

Example 1: T(n)=T(n/2)+n^2

 

After comparison a=1, b=2, k=2, p=0, f(n)= n^2. Now calculate log b a= log 2 1=0, k=2.

 

Compare with k: log 2 1 < k (case3).

 

Calculate time complexity:

 

log b a< k, then the value of T(n) depends upon the value of ‘p’. 

 

·        if(p>= 0) then T(n)= θ ((nk) (log p n)).

 

·        if(p< 0) then T(n)= θ (nk).

 

here condition 1 becomes satisfied hence, T(n)= θ ((n2) (log 0 n)).

 

 (log 0 n) is undefined.

 

Therefore, T(n)= θ (nk).

 

Time Complexity is T(n)= θ (n2).

 

 

 

Example 2: T(n)= 4T(n/2)+n^2

 

After comparison a=4, b=2, k=2, p=0, f(n)= n^2. Now calculate log b a= log 2 1=2, k=2.

 

Compare with k: log 2 1= 2=k (case 2).

 

log b a= k, then the value of T(n) depends upon the value of ‘p’.

 

if (p>-1) then T(n)= θ ((nk) (log (p+1) n)).

 

if (p= -1) then T(n)= θ ((nk) (log log n)).

 

                  if (p< -1) then T(n)= θ (nk).

if (p>-1) then T(n)= θ ((nk) (log (p+1) n)) is satisfied. Now put the values of k, p in condition.

 

Time Complexity is T(n)= θ ((n2) (log (0+1) n))= T(n)= θ [(n2) (log n)].

 

 

 

 

 

*    Here are some important points to remember about Master Theorem:

 

 

 

1.    Divide-and-conquer recurrences: The Master Theorem is specifically designed to solve recurrence relations that arise in the analysis of divide-and-conquer algorithms.

 

2.    Form of the recurrence: The Master Theorem applies to recurrence relations of the form T(n) = aT(n/b) + f(n), where a, b, and f(n) are positive functions and n is the size of the problem.

 

3.    Time complexity: The Master Theorem provides conditions for the solution of the recurrence to be in the form of O(n^k) for some constant k, and it gives a formula for determining the value of k.

 

4.    Advanced version: The advanced version of the Master Theorem provides a more general form of the theorem that can handle recurrence relations that are more complex than the basic form.

 

5.    Limitations: The Master Theorem is not applicable to all recurrence relations, and it may not always provide an exact solution to a given recurrence.

 

6.    Useful tool: Despite its limitations, the Master Theorem is a useful tool for analysing the time complexity of divide-and-conquer algorithms and provides a good starting point for solving more complex recurrences.

 

7.    Supplemented with other techniques: In some cases, the Master Theorem may need to be supplemented with other techniques, such as the substitution method or the iteration method, to completely solve a given recurrence relation.

 

 

 

*    Conclusion: In this article, we learnt about the master theorem (analysis of algorithms) and how we use it to directly find the time complexity of an algorithm containing recurrence relations.

 

 

 

 

 

 

Name : Nikeetaa Garrade