Master Theorem

Master Theorem

Master Theorem is a formula for solving recurrence relations is:

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

where,
n = size of input

a = no. of subproblems in recursion

n/b = size of each subproblem. All subproblems are supposed to have the same size.

f(n) = f(n)is the cost of the work done outside the recursive call and it contains the cost of dividing the problem and merging the solutions

Here, a ≥ 1 and b > 1 are the remains constants, and

f(n) is an asymptotically positive function.

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

The master theorem is used in calculating the time complexity of recurrence relations that is divide and conquer algorithms in a simple and easy way.

If a ≥ 1 and b > 1 are remains constants then

f(n) is an asymptotically positive function

Time complexity of a recursive relation is given by,

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

where, T(n) has the asymptotic bounds they are follows
1. f(n) = O(nlogb a-ϵ),  T(n) = Θ(nlogb a).
2.  f(n) = Θ(nlogb a),  T(n) = Θ(nlogb a *log n).
3.  f(n) = Ω(nlogb a+ϵ),  T(n) = Θ(f(n)).
ϵ > 0 is a constant.

:

Example of master theorem

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

Here,
a = 3
n/b = n/2
f(n) = n2
logba = log2 3 ≈ 1.58 < 2

ie. f(n) < nlogb a+ϵ , where, ϵ is a constant.

Case 3 implies here.

Thus, T(n) = f(n) = Θ(n2)

Read more, Asymptotic Notation