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) \\ \alpha f(n / b) & \le f(n), \alpha = a / c \\ \alpha f(n) & \le f(nb) \\ \alpha^i f(1) & \le f(b^i) \\ \end{aligned} $$

$$ \begin{aligned} n = b^i & \Rightarrow i = \log_b n \Rightarrow f(n) \ge \alpha^{\log_b n}f(1) = n^{\log_b \alpha} \\ \alpha > a & \Rightarrow \alpha = a + d \quad (c < 1, d > 0) \\ & \Rightarrow f(n) = n^{\log_b a + \log_b d} = n^{\log_b a+\epsilon}. \quad (\epsilon = \log_b d) \end{aligned} $$