Give a simple and exact expression for nj in equation (4.12) for the case in which b is a positive integer instead of an arbitrary real number.
Show that if  = \Theta(n^{\log_{b}{a}}) \lg^k{n} ) , where k ≥ 0, then the master recurrence has solution Show that if  = \Theta(n^{\log_{b}{a}}) \lg^{k+1}{n} ).
 = \sum_{j = 0}^{\log_{b}{n-1}} a^jf(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}) )
Show that case 3 of the master theorem is overstated, in the sense that the regularity condition af(n/b) ≤ cf(n) for some constant c < 1 implies that there exists a constant  = \Omega(n^{\log_b{a+\epsilon}})).
根据case3,我们有 \le cf(n) ~~~~ a \ge 1,b \ge 1 c < 1 )
变形一下
 \ge kf(n) ~~~where ~ k = a/c > a \\ \Rightarrow f(b^i) \ge k^i f(1) \\
if~~ n = b^i, i = \log_b{n}, then f(n) \ge k^{\log_b{n}}f(1) \\
k^{\log_b{n}} = n^{\log_b{k}} ~ and ~ \log_b{k} \ge \log_b{a} so \log_b{k} = \log_b{a} + \epsilon
)
Follow @louis1992 on github to help finish this task.