The master theorem concerns recurrence relations of the form:

$T(n) = aT\bigg(\frac{n}{b}\bigg) + f(n) \ \ where \ \ a \ge 1, b \gt 1$

In the application to the analysis of a recursive algorithm, the constants and function take on the following significance:

• n is the size of the problem.
• a is the number of subproblems in the recursion.
• n/b is the size of each subproblem.
• f (n) is the cost of the work done outside the recursive calls, which includes the cost of dividing the problem and the cost of merging the solutions to the subproblems.

It is possible to determine an asymptotic tight bound in these three cases:

Case 1

Generic form

If $f(n) € O(n^c)$ where $c\ltlog \frac{a}{b}$ (using big O notation) then:

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

Example

As one can see from the formula above:

$a = 8, b = 2, f(n) = 1000n^2, \ \ so \\ f(n) \epsilon \ \ O(n^c), \ \ where \ \ c = 2$

Next, we see if we satisfy the case 1 condition:

$log_b a = log_2 8 = 3 \gt c$

It follows from the first case of the master theorem that

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

(Indeed, the exact solution of the recurrence relation is, assuming).

$T(n) = 1001 n^3 - 1000n^2, \ \ assuming \ \ T(1) = 1$

Case 2

Generic form

If it is true, for some constant k ≥ 0, that:

$f(n) \epsilon \ \ \theta (n^c log^k n) \ \ where \ \ c = log_b a$

then:

$T(n) \epsilon \ \ \theta \ \ (n^c log^{k+1}n)$

Example

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

As we can see in the formula above the variables get the following values: . $a = 2, b = 2, f(n) = 10n \\ f(n) \theta (n^c log^k n), \ \ where \ \ c = 1, K = 0$

Next, we see if we satisfy the case 2 condition:

$log_b a = log_2 2 = 1$ and therefore yes, $c = log_b a$

So it follows from the second case of the master theorem:

$T(n) = \theta (n^{log_b a} log^{k+1}n) = \theta (n^1 log^1 n) = \theta (n log n)$

Thus the given recurrence relation T(n) was in Θ(n log n). (This result is confirmed by the exact solution of the recurrence relation, which is )

$T(n) = n + 10nlog_2 2 \ \ assuming \ \ T(1) = 1$

Case 3

Generic form

If it is true that:

$f(n) \epsilon \ \ \omega \ \ (n^c) \ \ where \ \ c \gt log_b a$

and if it is also true that

$a f \bigg(\frac{n}{b}\bigg) \le k f(n)$ for some constant k < 1 and sufficiently

Large n (often called the regularity condition) then:

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

Example

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

As we can see in the formula above the variables get the following values:

$a = 2, b = 2, f(n) = n^2, \ \ so \\ f(n) \omega (n^c), \ \ where \ \ c = 2$

Next, we see if we satisfy the case 3 condition:

$log_b a = log_2 2 = 1$ and therefore yes $c \gt log_b a$

The regularity condition also holds:

$2\bigg(\frac{n^2}{4}\bigg) \le kn^2 \ \ choosing \ \ k = 1/2$

So it follows from the third case of the master theorem:

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

Thus the given recurrence relation T(n) was in $Θ(n^2)$, that complies with the f (n) of the original formula.

(This result is confirmed by the exact solution of the recurrence relation, which is , assuming T(1)=1)