Master Theorem | Recurrences | Algorithms

Master Theorem


The master theorem concerns recurrence relations of the form:

In the application to the analysis of a recursive algorithm, the constants and function take on the following significance:

n is the size of the problem, a is the number of sub problems in the recursion, n/b is the size of each sub problem (Here it is assumed that all sub problems are essentially the same size.) and
f (n) is the cost of the work done outside the recursive calls, which includes the cost of dividing the problem and the cost of merging the solutions to the sub problems.

It is possible to determine an asymptotic tight bound in these three cases:

Master Theorem

Master Theorem

Master Theorem 

Master Theorem

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

In order to solve recurrence relations using Master’s theorem method, we compare a with bk.
Then we have to follow three cases shown below

Case 1
If a > bk ,then T(n) = θ (nlogba)

Case 2
If a = bk and
If p < -1, then T(n) = θ (nlogba)
If p = -1, then T(n) = θ (nlogba.log2n)
If p > -1, then T(n) = θ (nlogba.logp+1n)

Case 3
If a < bk and
If p < 0, then T(n) = O (nk)
If p >= 0, then T(n) = θ (nk.logpn)



Topic : Master Theorem | Recurrences | Algorithms

This article is contributed by A.S Karthik if You find any mistake please comment below in comment section.Article will be updated regularly

Refer Gate questions on algorithms

Leave a Reply