What is the Master theorem🤔 in Data structure? | Learn DSA.

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 size of input.
• a is the number of sub-problems in the recursion.
• n/b is the size of each sub-problem (all sub-problems are assumed to have the same size.)
• f(n) is an asymptotically positive function, 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.
  (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).
• a ≥ 1 and b > 1 are constants.

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)