# What is the Master theoremđź¤” in Data structure? | Learn DSA.

1 min readAug 3, 2023

The master theorem or master method is a formula for solving recurrence relations. The master method is used to solve the following types of recurrence:

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

## Where

**n**

is the number of sub-problems in the recursion.**a**

is the size of each sub-problem (all sub-problems are assumed to have the same size.)**n/b****f(n)**

is the sum of work done outside the recursive call, which includes the sum of dividing the problems and sum of combining the solution to the sub-problem.**f(n)**

(to better understand this divide & combine check: the Divide and Conquer Algorithm)- An asymptotically positive function means that for a large value of n, we should have
`f(n) > 0`

(positive function).

and**a â‰Ą 1**

are constants.**b > 1**

The master theorem is the simple and quick way to calculate the time complexity of recurrence relations. check: The Divide and conquer algorithm is an example of recurrence relations.

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