What is the master's theorem?

Overview

The master’s theorem is one of the best and reasonably practical approaches to solve recurrence equations because it directly provides us with the cost of the algorithm. This method applies to the recurrence equations that are in the following form:

$$T(n) = aT(\frac{n}{b}) + f(n)$$

Constraints

The following are some of the constraints of the equation of master’s theorem:

• a represents the number of subproblems in the recursion, and it must be greater or equal to one (a >= 1).
• n/b is assumed to have the same size for each subproblem, and b must be greater than one (b > 1) to ensure a proper divide and conquer recurrence analysis.
• f(n) must be an asymptotically positive function and it is mainly a cost of operations performed other than recursive calls, which includes the cost of dividing the problem and then the cost of merging solutions.

Limitations

We cannot apply the master’s theorem in the following cases:

• T(n) is not monotone.
• f(n) is not a polynomial.
• a is not a constant.

Time complexity comparison

The following are some of the asymptotic bounds of T(n):

$$T(n) = aT(\frac{n}{b}) + f(n)$$

Case 1: If the cost of solving the subproblems increases by a certain factor at each level, then:

$$f(n) < n^{log_b^{a}}$$

$$T(n) = \theta(n^{log_b^{a}})$$

Case 2: If the cost of solving the subproblems is nearly equal at each level, then:

$$f(n) = n^{log_b^{a}}$$

$$T(n) = \theta(n^{log_b^{a}} * log \space n)$$

Case 3: If the cost of solving the subproblems decreases by a certain factor at each level, then:

$$f(n) > n^{log_b^{a}}$$

$$T(n) = \theta(f(n))$$

Examples

Let’s jump right into the mathematics of the master’s theorem:

Case 1

$$T(n) = 4T(\frac{n}{2}) + n$$

Given values:

$$a = 4, \space b = 2, \space f(n) = n$$

Substituting the values of a and b:

$$n^{log_b^{a}} = n^{log_2^{4}} = n^2$$

This satisfies case 1:

$$f(n) < n^{log_b^{a}}$$

$$T(n) = \theta(n^{log_b^{a}})$$

Final answer:

$$T(n) = \theta(n^2)$$

Case 2

$$T(n) = 2T(\frac{n}{2}) + n$$

Given values:

$$a = 2, \space b = 2, \space f(n) = n$$

Substituting the values of a and b:

$$n^{log_b^{a}} = n^{log_2^{2}} = n$$

This satisfies case 2:

$$f(n) = n^{log_b^{a}}$$

$$T(n) = \theta(n^{log_b^{a}} * log \space n)$$

Final answer:

$$T(n) = \theta(n \space log \space n)$$