MASTER THEOREM

What is master theorem?

Master theorem is a method which is used to calculate time complexities of algorithms. In analysis, time complexities are calculated to find out the best optimal logic of an algorithm. Master’s theorem is applied on recurrence relations.

Recurrence relations

Let's get familiar with recurrence relations before going into the Master Theorem. The time complexity of algorithms is expressed mathematically in terms of smaller instances of the same problem. The Fibonacci sequence, in which each term is the sum of the two terms before it, is a well-known example.

General Format of master theorem is-

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

where a≥1 ,b>1 and f(n) should be +ve always.

where,

·        n is the size of the problem.

·        a is the number of subproblems in the recursion.

·        n/b is the size of each subproblem. (Here it is assumed that all subproblems are essentially the same size.)

·        f (n) is the sum of the work done outside the recursive calls, which includes the sum of dividing the problem and the sum of combining the solutions to the subproblems.

·        It is not possible always bound the function according to the requirement, so we make three cases which will tell us what kind of bound we can apply on the function.

 

Cases:

1.      f (n)< n^log_b^a   [T(n)=Θ(n^log_b^a )]

2.      f (n)= n^log_b^a   [T(n)=Θ(n^log_b^a ).log n]

3.      f (n)>n^log_b^a   [T(n)=Θ f(n)]

 

Examples:

1)T(n)=4T(n/2)+n

Given: a=4

            b=2

            f(n)=n

Solution-

n ^log_b^a = n^log₂⁴=n²

f(n)< n ^log_b^a                                         . . . case1

T(n)= Θ (n²)

 

2)T(n)=2T(n/2)+n

Given: a=2

            b=2

            f(n)=n

Solution-

n ^log_b^a = n^log₂²=n

f(n)= n^log_b^a                                 . . . case 2

T(n)= Θ (n²)

Name : Aachal Khodape

Roll No. :  23