Master theorem is used to analyze complexity of many problems in divide and conquer category.

Master theorem deals with recurrence relations in the form:

where:

f(n) is the time required to conquer(dividing or merging) the sub-problems;

such as merging in merge sort or finding pivot in quick sort</em>

There are 3 cases to solve such kind of recurrences:

In each of three cases we compare f(n) with (n

If f(n) = O( n

then solution becomes T(n) = θ(n

In first case, comparison states that (n

T(n) = 9T(n/3)+1000n

a=9, b=3, f(n)=n

n

Hence solution T(n) = θ(n

if f(n) = θ(n

then solution becomes T(n) = θ(n

In second case, comparison states that (n

T(n) = T(n/2)+c (Binary search)

a=1, b=2, f(n)=c (constant)

n

Hence solution T(n) = θ(logn)

if f(n) = Ω( n

and it is also true that af(n/b) <= kf(n) for some constant k < 1,

and sufficiently large n.

then solution becomes T(n) = θ( f(n) )

In third case comparison states that (n

hence solution θ( f(n) )

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

n

Hence solution T(n) = θ(n

Master theorem doesn't apply if function is not polynomially large enough to determine solution.

eg : T(n) = 2T(n/2)+nlogn here a=2,b=2

f(n) = n logn;

n

so f(n) is greater than n

Master theorem deals with recurrence relations in the form:

**T(n)= aT(n/b)+f(n)**where:

*n is size of original problem**a is number of sub-problems**n/b size of sub-problems(assuming sub-problems of equal size)*f(n) is the time required to conquer(dividing or merging) the sub-problems;

such as merging in merge sort or finding pivot in quick sort</em>

There are 3 cases to solve such kind of recurrences:

In each of three cases we compare f(n) with (n

^{logba}). Polynomially larger of these functions determines solution.__Case 1:__If f(n) = O( n

^{c}) where c < log_{b}athen solution becomes T(n) = θ(n

^{logba})In first case, comparison states that (n

^{logba}) is larger than f(n),hence solution θ(n^{logba})__For example__:T(n) = 9T(n/3)+1000n

^{2}a=9, b=3, f(n)=n

^{2}(leaving constant terms)n

^{logba}= n^{log39}= n^{3}which is polynomially greater than n^{2}.Hence solution T(n) = θ(n

^{3})**Case 2:**if f(n) = θ(n

^{log b a })then solution becomes T(n) = θ(n

^{logba}logn)In second case, comparison states that (n

^{logba}) is equal to f(n), we multiply f(n) by logarithmic factor hence solution θ(n^{logba}logn)__For example__:T(n) = T(n/2)+c (Binary search)

a=1, b=2, f(n)=c (constant)

n

^{logba}= n^{log21}= n^{0}= 1 which is equal to f(n).Hence solution T(n) = θ(logn)

**Case 3:**if f(n) = Ω( n

^{c}) where c > log_{b}aand it is also true that af(n/b) <= kf(n) for some constant k < 1,

and sufficiently large n.

then solution becomes T(n) = θ( f(n) )

In third case comparison states that (n

^{logba}) is smaller than f(n).hence solution θ( f(n) )

__For example__:T(n) = 2T(n/2)+10n

^{2}a=2, b=2, f(n)=n^{2}(leaving constant terms)n

^{logba}= n^{log22}= n which is polynomially smaller than n^{2}.Hence solution T(n) = θ(n

^{2})**Facts**:Master theorem doesn't apply if function is not polynomially large enough to determine solution.

eg : T(n) = 2T(n/2)+nlogn here a=2,b=2

f(n) = n logn;

n

^{logba}= n;so f(n) is greater than n

^{logba}but not polynomially large enough, its large by a factor of logarithm hence can't determine solution.