In this tutorial, you will learn what master theorem is and how it is used for solving recurrence relations.

The master method is a formula for solving recurrence relations of the form:

T(n) = aT(n/b) + f(n), where, n = size of input a = number of subproblems in the recursion n/b = size of each subproblem. All subproblems are assumed to have the same size. f(n) = cost of the work done outside the recursive call, which includes the cost of dividing the problem and cost of merging the solutions Here, a ≥ 1 and b > 1 are constants, and f(n) is an asymptotically positive function.

An asymptotically positive function means that for a sufficiently large value of `n`, we have `f(n) > 0`

.

The master theorem is used in calculating the time complexity of recurrence relations (

divide and conquer algorithms) in a simple and quick way.

## 1. Master Theorem

If `a ≥ 1`

and `b > 1`

are constants and `f(n)`

is an asymptotically positive function, then the time complexity of a recursive relation is given by

T(n) = aT(n/b) + f(n) where, T(n) has the following asymptotic bounds: 1. If f(n) = O(n^{logb a-ϵ}), then T(n) = Θ(n^{logb a}). 2. If f(n) = Θ(n^{logb a}), then T(n) = Θ(n^{logb a}* log n). 3. If f(n) = Ω(n^{logb a+ϵ}), then T(n) = Θ(f(n)). ϵ > 0 is a constant.

Each of the above conditions can be interpreted as:

- If the cost of solving the sub-problems at each level increases by a certain factor, the value of
`f(n)`

will become polynomially smaller than`n`

. Thus, the time complexity is oppressed by the cost of the last level ie.^{logb a}`n`

^{logb a} - If the cost of solving the sub-problem at each level is nearly equal, then the value of
`f(n)`

will be`n`

. Thus, the time complexity will be^{logb a}`f(n)`

times the total number of levels ie.`n`

^{logb a}* log n - If the cost of solving the subproblems at each level decreases by a certain factor, the value of
`f(n)`

will become polynomially larger than`n`

. Thus, the time complexity is oppressed by the cost of^{logb a}`f(n)`

.

## 2. Solved Example of Master Theorem

T(n) = 3T(n/2) + n2 Here, a = 3 n/b = n/2 f(n) = n^{2}log_{b}a = log_{2}3 ≈ 1.58 < 2 ie. f(n) < n^{logb a+ϵ}, where, ϵ is a constant. Case 3 implies here. Thus, T(n) = f(n) = Θ(n^{2})

## 3. Master Theorem Limitations

The master theorem cannot be used if:

`T(n)`is not monotone. eg.`T(n) = sin n`

`f(n)`

is not a polynomial. eg.`f(n) = 2`

^{n}`a`is not a constant. eg.`a = 2n`

`a < 1`

### Related posts:

Breadth first search

Bucket Sort Algorithm

Heap Sort Algorithm

Perfect Binary Tree

Linear Search

Tree Data Structure

Deletion from a B-tree

Pick's Theorem - area of lattice polygons

Deque Data Structure

Floyd-Warshall Algorithm

Radix Sort Algorithm

Why Learn Data Structures and Algorithms?

Binary Search Tree (BST)

Data Structure and Types

Ford-Fulkerson Algorithm

B+ Tree

Kruskal's Algorithm

Greedy Algorithm

Divide and Conquer Algorithm

Merge Sort Algorithm

Decrease Key and Delete Node Operations on a Fibonacci Heap

Fibonacci Heap

Insertion in a Red-Black Tree

Balanced Binary Tree

Priority Queue

AVL Tree

Heap Data Structure

Insertion Sort Algorithm

Circular Queue Data Structure

Hash Table

Types of Queues

Bellman Ford's Algorithm