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\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用