> For the complete documentation index, see [llms.txt](https://vikram-bajaj.gitbook.io/cs-gy-6033-i-design-and-analysis-of-algorithms-1/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://vikram-bajaj.gitbook.io/cs-gy-6033-i-design-and-analysis-of-algorithms-1/main/algorithm-analysis/master-method.md).

# 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.