4.5 The master method for solving recurrences

4.5-1

Use the master method to give tight asymptotic bounds for the following recurrences:

a. $T(n) = 2T(n / 4) + 1$.

b. $T(n) = 2T(n / 4) + \sqrt n$.

c. $T(n) = 2T(n / 4) + n$.

d. $T(n) = 2T(n / 4) + n^2$.

a. $\Theta(n^{\log_4 2}) = \Theta(\sqrt n)$.

b. $\Theta(n^{\log_4 2}\lg n) = \Theta(\sqrt n\lg n)$.

c. $\Theta(n)$.

d. $\Theta(n^2)$.

4.5-2

Professor Caesar wishes to develop a matrix-multiplication algorithm that is asymptotically faster than Strassen's algorithm. His algorithm will use the divide-and-conquer method, dividing each matrix into pieces of size $n / 4 \times n / 4$, and the divide and combine steps together will take $\Theta(n^2)$ time. He needs to determine how many subproblems his algorithm has to create in order to beat Strassen's algorithm. If his algorithm creates $a$ subproblems, then the recurrence for the running time $T(n)$ becomes $T(n) = aT(n / 4) + \Theta(n^2)$. What is the largest integer value of $a$ for which Professor Caesar's algorithm would be asymptotically faster than Strassen's algorithm?

Strassen's algorithm has running time of $\Theta(n^{\lg 7})$.

The largest integer $a$ such that $\log_4 a < \lg 7$ is $a = 48$.

4.5-3

Use the master method to show that the solution to the binary-search recurrence $T(n) = T(n / 2) + \Theta(1)$ is $T(n) = \Theta(\lg n)$. (See exercise 2.3-5 for a description of binary search.)

$$ \begin{aligned} a & = 1, b = 2, \\ f(n) & = \Theta(n^{\lg 1}) = \Theta(1), \\ T(n) & = \Theta(\lg n). \end{aligned} $$

4.5-4

Can the master method be applied to the recurrence $T(n) = 4T(n / 2) + n^2\lg n$? Why or why not? Give an asymptotic upper bound for this recurrence.

With $a = 4$, $b = 2$, we have $f(n) = n^2\lg n \ne O(n^{2 - \epsilon}) \ne \Omega(n^{2 + \epsilon})$, so we cannot apply the master method.

We guess $T(n) \le cn^2\lg^2 n$, subsituting $T(n/2) \le c(n/2)^2\lg^2 (n/2)$ into the recurrence yields

$$ \begin{aligned} T(n) & = 4T(n / 2) + n^2\lg n \\ & \le 4c(n / 2)^2\lg^2(n / 2) + n^2\lg n \\ & = cn^2\lg(n / 2)\lg n - cn^2\lg(n / 2)\lg 2 + n^2\lg n \\ & = cn^2\lg^2 n - cn^2\lg n\lg 2 - cn^2\lg(n / 2)\lg 2 + n^2\lg n \\ & = cn^2\lg^2 n + (1 - c\lg 2)n^2\lg n - cn^2\lg(n / 2)\lg 2 & (c \ge 1/\lg 2) \\ & \le cn^2\lg^2 n - cn^2\lg(n / 2)\lg 2 \\ & \le cn^2\lg^2 n. \end{aligned} $$

Exercise 4.6-2 is the general case for this.

4.5-5 $\star$

Consider the regularity condition $af(n / b) \le cf(n)$ for some constant $c < 1$, which is part of case 3 of the master theorem. Give an example of constants $a \ge 1$ and $b > 1$ and a function $f(n)$ that satisfies all the conditions in case 3 of the master theorem, except the regularity condition.

$a = 1$, $b = 2$ and $f(n) = n(2 - \cos n)$.

If we try to prove it,

$$ \begin{aligned} \frac{n}{2}(2 - \cos\frac{n}{2}) & < cn \\ \frac{1 - cos(n / 2)}{2} & < c \\ 1 - \frac{cos(n / 2)}{2} & \le c. \end{aligned} $$

Since $\min\cos(n / 2) = -1$, this implies that $c \ge 3 / 2$. But $c < 1$.