跳转至

4.6 Proof of the master theorem

4.6-1 \(\star\)

Give a simple and exact expression for \(n_j\) in equation \(\text{(4.27)}\) for the case in which \(b\) is a positive integer instead of an arbitrary real number.

We state that \(\forall{j \ge 0}, n_j = \left \lceil \frac{n}{b^j} \right \rceil\).

Indeed, for \(j = 0\) we have from the recurrence's base case that \(n_0 = n = \left \lceil \frac{n}{b^0} \right \rceil\).
Now, suppose \(n_{j - 1} = \left \lceil \frac{n}{b^{j - 1}} \right \rceil\) for some \(j > 0\). By definition, \(n_j = \left \lceil \frac{n_{j - 1}}{b} \right \rceil\).
It follows from the induction hypothesis that \(n_j = \left \lceil \frac{\left \lceil \frac{n}{b^{j - 1}} \right \rceil}{b} \right \rceil\).
Since \(b\) is a positive integer, equation \(\text{(3.4)}\) implies that \(\left \lceil \frac{\left \lceil \frac{n}{b^{j - 1}} \right \rceil}{b} \right \rceil = \left \lceil \frac{n}{b^j} \right \rceil\).
Therefore, \(n_j = \left \lceil \frac{n}{b^j} \right \rceil\).

P.S. \(n_j\) is obtained by shifting the base \(b\) representation \(j\) positions to the right, and adding \(1\) if any of the \(j\) least significant positions are non-zero.

4.6-2 \(\star\)

Show that if \(f(n) = \Theta(n^{\log_b a}\lg^k{n})\), where \(k \ge 0\), then the master recurrence has solution \(T(n) = \Theta(n^{\log_b a}\lg^{k + 1}n)\). For simplicity, confine your analysis to exact powers of \(b\).

\[ \begin{aligned} g(n) & = \sum_{j = 0}^{\log_b n - 1} a^j f(n / b^j) \\\\ f(n / b^j) & = \Theta\Big((n / b^j)^{\log_b a} \lg^k(n / b^j) \Big) \\\\ g(n) & = \Theta\Big(\sum_{j = 0}^{\log_b n - 1}a^j\big(\frac{n}{b^j}\big)^{\log_b a}\lg^k\big(\frac{n}{b^j}\big)\Big) \\\\ & = \Theta(A) \\\\ A & = \sum_{j = 0}^{\log_b n - 1} a^j \big(\frac{n}{b^j}\big)^{\log_b a}\lg^k\frac{n}{b^j} \\\\ & = n^{\log_b a} \sum_{j = 0}^{\log_b n - 1}\Big(\frac{a}{b^{\log_b a}}\Big)^j\lg^k\frac{n}{b^j} \\\\ & = n^{\log_b a}\sum_{j = 0}^{\log_b n - 1}\lg^k\frac{n}{b^j} \\\\ & = n^{\log_b a} B \\\\ \lg^k\frac{n}{d} & = (\lg n - \lg d)^k = \lg^k{n} + o(\lg^k{n}) \\\\ B & = \sum_{j = 0}^{\log_b n - 1}\lg^k\frac{n}{b^j} \\\\ & = \sum_{j = 0}^{\log_b n - 1}\Big(\lg^k{n} - o(\lg^k{n})\Big) \\\\ & = \log_b n\lg^k{n} + \log_b n \cdot o(\lg^k{n}) \\\\ & = \Theta(\log_b n\lg^k{n}) \\\\ & = \Theta(\lg^{k + 1}{n}) \\\\ g(n) & = \Theta(A) \\\\ & = \Theta(n^{\log_b a}B) \\\\ & = \Theta(n^{\log_b a}\lg^{k + 1}{n}). \end{aligned} \]

4.6-3 \(\star\)

Show that case 3 of the master method is overstated, in the sense that the regularity condition \(af(n / b) \le cf(n)\) for some constant \(c < 1\) implies that there exists a constant \(\epsilon > 0\) such that \(f(n) = \Omega(n^{\log_b a + \epsilon})\).

\[ \begin{aligned} af(n / b) & \le cf(n) \\\\ \Rightarrow f(n / b) & \le \frac{c}{a} f(n) \\\\ \Rightarrow f(n) & \le \frac{c}{a} f(bn) \\\\ & = \frac{c}{a} \left(\frac{c}{a} f(b^2n)\right) \\\\ & = \frac{c}{a} \left(\frac{c}{a}\left(\frac{c}{a} f(b^3n)\right)\right) \\\\ & = \left(\frac{c}{a}\right)^i f(b^i n) \\\\ \Rightarrow f(b^i n) & \ge \left(\frac{a}{c}\right)^i f(n). \end{aligned} \]

Let \(n = 1\), then we have

\[f(b^i) \ge \left(\frac{a}{c}\right)^i f(1) \quad (*).\]

Let \(b^i = n \Rightarrow i = \log_b n\), then substitue back to equation \((*)\),

\[ \begin{aligned} f(n) & \ge \left(\frac{a}{c}\right)^{\log_b n} f(1) \\\\ & \ge n^{\log_b \frac{a}{c}} f(1) \\\\ & \ge n^{\log_b a + \epsilon} & \text{ where $\epsilon > 0$ because $\frac{a}{c} > a$ (recall that $c < 1$)} \\\\ & = \Omega(n^{\log_b a + \epsilon}). \end{aligned} \]
本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用