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)
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.
If f(n) = O(), then T(n) = ()
If f(n) = (), then T(n) = (. lg n)
If f(n) = (), then T(n) = (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.