Master Theorem and Formulas for Recurrence Relation

Master Theorem for Divide-and-Conquer Recurrence Relations

The Master Theorem is a powerful tool for analyzing the time complexity of divide-and-conquer algorithms. It provides a straightforward way to solve recurrence relations of the form:

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

where $a \geq 1$ and $b > 1$.

To apply the Master Theorem, we first identify the values of $a$ and $b$ from the recurrence relation. We also express $f(n)$ in the form:

$f(n) = \Theta(n^k \log^p n)$

Here, $k$ and $p$ are constants that describe the asymptotic behavior of $f(n)$. Specifically:

• $k$ is the exponent of $n$, indicating the polynomial part of $f(n)$.
• $p$ is the exponent of $\log n$, indicating the logarithmic part of $f(n)$.

To determine the values of $k$ and $p$, you need to express $f(n)$ in its asymptotic form. For example:

• If $f(n) = n^3$, then $k = 3$ and $p = 0$.
• If $f(n) = n \log n$, then $k = 1$ and $p = 1$.
• If $f(n) = \frac{n}{\log n}$, then $k = 1$ and $p = -1$.

We then compare two key values: $\log_b a$ and $k$.

Case 1: $\log_b a > k$

If $\log_b a$ is greater than $k$, the solution to the recurrence relation is:

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

For Example:

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

Here, $a = 2$ and $b = 2$. So, $\log_2 2 = 1$ and $k = 0$.

Since $1 > 0$, this falls under Case 1:

$T(n) = \Theta(n)$

Case 2: $\log_b a = k$

If $\log_b a$ is equal to $k$, the solution depends on the value of $p$.

Subcase 2a: If $p > -1$,

$T(n) = \Theta(n^k \log^{p+1} n)$

Subcase 2b: If $p = -1$,

$T(n) = \Theta(n^k \log \log n)$

Subcase 2c: If $p < -1$,

$T(n) = \Theta(n^k)$

For Example:

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

Here, $a = 2$ and $b = 2$. So, $\log_2 2 = 1$ and $k = 1$.

Since $p = 0$, this falls under Subcase 2a:

$T(n) = \Theta(n \log n)$

Case 3: $\log_b a < k$

If $\log_b a$ is less than $k$, the solution is:

$T(n) = \Theta(n^k)$

For Example:

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

Here, $a = 1$ and $b = 2$. So, $\log_2 1 = 0$ and $k = 2$.

Since $0 < 2$, this falls under Case 3:

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

Additional Examples and Explanation

Let us solve a few more examples to solidify the understanding of the Master Theorem:

Example 1:

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

Here, $a = 4$ and $b = 2$. So, $\log_2 4 = 2$ and $k = 1$.

Since $2 > 1$, this falls under Case 1:

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

Example 2:

$T(n) = 8T\left(\frac{n}{2}\right) + n^3$

Here, $a = 8$ and $b = 2$. So, $\log_2 8 = 3$ and $k = 3$.

Since $3 = 3$, this falls under Case 2a (with $p = 0$):

$T(n) = \Theta(n^3 \log n)$

Example 3:

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

Here, $a = 2$ and $b = 2$. So, $\log_2 2 = 1$ and $k = 1$.

Since $p = -1$, this falls under Case 2b:

$T(n) = \Theta(n \log \log n)$