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.