$\star$ 4.6 Proof of the continuous master theorem

4.6-1

Show that $\sum_{j=0}^{\lfloor \log_{b}n\rfloor}(\log_{b} n-j)^k=\Omega(\log_b^{k+1}n)$.

$$ \begin{aligned} \sum_{j=0}^{\lfloor \log_{b}n\rfloor}(\log_{b} n-j)^k & \geq \sum_{j=0}^{\lfloor \log_{b}n\rfloor}(\lfloor \log_{b}n\rfloor n-j)^k\cr & = \sum_{j=0}^{\lfloor \log_{b}n\rfloor}(j)^k\cr & \geq \sum_{j=0}^{\log_{b}n-1}(j)^k\cr & = \Theta((\log_{b}n-1)^{k+1})\cr & = \Omega(\log_b^{k+1}n)\cr \end{aligned} $$

$\star$ 4.6-2

Show that case 3 of the master theorem is overstated (which is also why case 3 of Lemma 4.3 does not require that $f(n)=\Omega(n^{\log_b a+\epsilon})$) in the sense that the regularity condition $af(n/b)\leq cf(n)$ for some constant $c<1$ implies that there exists a constant $\epsilon > 0$ sunch that $f(n)=\Omega(n^{\log_b a+\epsilon})$.

$$ \begin{aligned} & af(n/b) \leq cf(n)\cr \implies & f(n)\geq \frac{a}{c}f(n/b)\cr \implies & f(n) \geq (\frac{a}{c})^i f(n/{b^i})\cr & \text{let } n=b^i\cr \implies & f(n)\geq (\frac{a}{c})^{\log_{b}n}f(1)\cr \implies & f(n) \geq n^{\log_{b}\frac{a}{c}}\cr & \because c<0,\therefore \frac {a}{c}=a+\epsilon \text{ for some constant }\epsilon >0\cr \implies & f(n)=\Omega(n^{\log_{b}a+\epsilon})\cr \end{aligned} $$

$\star$ 4.6-3

For $f(n)=\Theta(n^{\log_b a}/\lg n)$, prove that the summation in equation (4.19) has solution $g(n)=\Theta(n^{\log_b{a}}\lg\lg n)$. Conclude that a master recurrence $T(n)$ using $f(n)$ as its driving function has solution $T(n) = \Theta(n^{\log_b a}\lg\lg n)$.

$$ \begin{aligned} & \text{let }n=b^i\cr g(n) = & \sum_{j=0}^{i}a^jf(n/b^j)\cr = & \sum_{j=0}^{i}a^jf(b^{i-j})\cr = & \sum_{j=0}^{i}a^j\Theta(a^{i-j}/(i-j))\cr = & \sum_{j=0}^{i}a^i\Theta(1/j)\cr = & a^i\Theta(\lg i)\cr = & \Theta(a^{\log_{b}n} \lg\log_{b}n)\cr = & \Theta(n^{\log_{b}a} \lg\lg n)\cr g(bn) = & \Theta((bn)^{\log_{b}a} \lg\lg bn)=(n^{\log_{b}a} \lg\lg n)\cr \implies g(n)=& (n^{\log_{b}a} \lg\lg n)\text{ even if }n \neq b^i\cr \end{aligned} $$

We can concluded that $T(n)=g(n)+n^{\log_{b}a}=n^{\log_{b}a} \lg\lg n$.