Web
Analytics Made Easy - StatCounter

Solving Recurrence Relations (Part II)

Introduction

In the previous article, we discussed various methods to solve the wide variety of recurrence relations. In this article, we are going to talk about two methods that can be used to solve the special kind of recurrence relations known as divide and conquer recurrences. Those two methods solve the recurrences almost instantly. These two methods are called Master Method and Akra-Bazzi method.

The master method is applicable for special kind of divide and conquer recurrences whereas the Akra-Bazzi method is applicable for all kinds of divide and conquer recurrences. Akra-Bazzi method can be considered as a generalization of the Master Method.

I strongly recommend reading the following article before.

The Master method

The Master method is applicable for solving recurrences of the form
$$\begin{align} T(n) = aT\left (\frac{n}{b} \right) + f(n) \end{align}$$
where $a \ge 0$ and $b \ge 1$ are constants and $f(n)$ is an asymptotically positive function. Depending upon the value of $a, b$ and function $f(n)$, the master method has three cases.

  1. If $f(n) = O(n^{\log_b a-\epsilon})$ for some constant $\epsilon > 0$, then $T(n) = \Theta(n^{\log_b a})$.
  2. If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a}\log n)$.
  3. If $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some constant $\epsilon > 0$, and if $af(n/b) \le cf(n)$ for some constant $c < 1$ and all sufficiently large n, then $T(n) = \Theta(f(n)$.

If we memorize these three cases, we can solve many divide and conquer recurrences quite easily. Basically in master method, we check if $f(n)$ is upper, tight or lower bound on $n^{\log_b a}$. If it is upper bound, then we use case 1. If it is a tight bound, we use case 2 and if it is a lower bound, we use case 3. Now we will use The Master method to solve some of the recurrences.

Example 1: Consider a recurrence,
$$T(n) = 2T(n/4) + 1$$
The recurrence relation is in the form given by (1), so we can use the master method. Comparing it with (1), we get
$$a = 2, b = 4 \text{ and } f(n) = 1$$
Next we calculate $n^{\log_b a} = n^{\log_4 2} = n^{0.5}$. Since $f(n) = O(n^{0.5 - 0.1})$, where $\epsilon = 0.1$, we can apply the case 1 of the master method. Therefore,
$$T(n) = \Theta(n^{\log_b a}) = \Theta(n^{0.5})$$

Example 2: Consider,
$$T(n) = T(n/2) + \Theta(1)$$
For this recurrence, we have $a = 1, b = 2, f(n) = \Theta(1)$ and $n^{\log_b a} = n^0 = 1$. Since $f(n) = \Theta(1)$, we can use the case 2 of the master method. Therefore,
$$T(n) = \Theta(n^{\log_b a}\log n) = \Theta(\log n)$$

Example 3: Consider,
$$T(n) = 3T(n/4) + n\log n$$
For this recurrence, we have $a = 3, b = 4, f(n) = n\log n$ and $n^{\log_b a} = n^{\log_4 3}$. Since $f(n) = \Omega(n^{\log_4 3 + 0.01})$, this is the third case of master method. In case 3, we need additional checking i.e. we need $c < 1$ such that $af(n/b) \le cf(n)$.

$$af(n/b) = 3n/4\log (n/4) \le cn\log n \text{ if } c = 3/4$$

Therefore, the solution is (case 3)
$$T(n) = \Theta(f(n)) = \Theta(n\log n)$$

There are some recurrences, which appear to have the proper form for the master method but we can not use the master method to solve them.

Example 4: Consider a recurrence,
$$T(n) = 4T(n/2) + n^2\log n$$
In this recurrence, $a = 4, b = 2, f(n) = n^2\log n$, and thus, we have that $n^{\log_b a} = n^{\log_2 4} = n^2$. We can clearly see that $f(n) = n^2\log n = \Omega(n^2)$ and we may be tempted to use case 3. But hold on, we need a small positive number $\epsilon$ such that $n^2\log n = \Omega(n^{2 + \epsilon})$. Since $n^2\log n$ is not polynomially larger than $n^2$, we can not find such $\epsilon$. Consequently, we can not use master method to solve this example.

The Akra-Bazzi method

The master method does not apply to a recurrence such as
$$T(n) = T(n/3) + T(2n/3) + O(n)$$
In such case, we use another more powerful and general method known as Akra-Bazzi method. The Akra-Bazzi method solves the recurrence relation of the form
$$\begin{align}T(n) = \sum_{i = 1}^k a_iT(b_in) + f(n) \end{align}$$
where,

  • $a_i > 0$ is a constant for $i \le i \le k$
  • $b_i \in (0, 1)$ is a constant for $1 \le i \le k$
  • $k \ge 1$ is a constant and,
  • $f(n)$ is non-negative function

The solution of recurrence given in (2) is,
$$T(n) = \Theta\left(n^p \left( 1 + \int_{1}^{n} \frac{f(u)}{u^{p + 1}} du \right ) \right)$$
Provided,
$$\sum_{i = 1}^{k}a_ib_i^p = 1 \text{ where $p$ is a unique real number.}$$

Example 1: Consider a recurrence,
$$T(n) = 2T(n/4) + 3T(n/6) + \Theta(n\log n)$$

For this recurrence, $a_1 = 2, b_1 = 1/4, a_2 = 3, b_2 = 1/6, f(n) = n\log n$. The value of $p$ can be calculated as,
$$a_1b_1^p + a_2b_2^p = 2\times(1/4)^p + 3\times (1/6)^p = 1$$
$p = 1$ satisfies the above equation. The solution is
$$\begin{align} T(n) &= \Theta\left(n^p \left( 1 + \int_{1}^{n} \frac{f(u)}{u^{p + 1}} du \right ) \right)\\
& = \Theta\left(n \left( 1 + \int_{1}^{n} \frac{u\log u}{u^2} du \right ) \right) \\
&= \Theta\left(n \left( 1 + \frac{\log^2n}{2} \right ) \right)\\
&= \Theta(n\log^2n)
\end{align}$$

References

  1. Akra, M., & Bazzi, L. (1998). On the Solution of Linear Recurrence Equations. Computational Optimization and Applications, 10, 195-210. Retrieved September 16, 2018, from http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/LinearRecurrenceEquations.pdf
  2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (n.d.). Introduction to algorithms (3rd ed.). The MIT Press.