# Master Theorem

The Master Theorem can be used to calculate the time complexity of a recurrence relation.

Recurrence relations are of the form:

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

where:

n = number of inputs/problem

a = number of subproblems

n/b = size of each subproblem

f(n) = time to divide and combine results

The Master Theorem works only if a.f(n/b) <= c.f(n) where c<1. This is the **regularity condition**.

## Case 1:

If f(n) = O($$n^{log_ba}$$), then T(n) = $$\Theta$$($$n^{log_ba}$$)

## Case 2:

If f(n) = $$\Theta$$($$n^{log_ba}$$), then T(n) = $$\Theta$$($$n^{log_ba}$$. lg n)

## Case 3:

If f(n) = $$\Omega$$($$n^{log_ba}$$), then T(n) = $$\Theta$$(f(n))

**NOTE**: The Master Theorem **doesn't work** for recurrence relations of the form **T(n) = kT(n/k) + n.lgn** because there is no polynomial difference between the recursive and function terms i.e. kT(n/k) and n.lgn respectively.
