I am trying to go through the proof of the Master Theorem in Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, "Introduction to Algorithms (2nd or 3rd Ed.)" where it shows the problem size doesn't have to be an exact power of $b$.
Here is an extensive quote (from the 2nd Ed., with some emphases added) to make this question self-contained; the question itself is at the end.
4.4.1 The proof for exact powers
[…]
Lemma 4.3
Let $a \ge 1$ and $b>1$ be constants, and let $f(n)$ be a nonnegative function defined on exact powers of $b$. A function $g(n)$ defined over exact powers of $b$ by $$
g(n) = \sum^{\log_b n – 1}_{j=0} a^j f(n/b^j) \;\;\;\;\;(4.7)
$$
can then be bounded asymptotically for exact powers of $b$ as follows.[…]
[case] 2. If$f(n) = \Theta(n^{\log_b a})$, then $g(n) = \Theta(n^{\log_b a} \lg n)$ .
[…]
Proof […]
Under the assumption that $f(n) = \Theta(n^{\log_b a})$ for case 2, we have that $f(n/b^j) = \Theta((n/b^j)^{\log_b a})$. Substituting into equation (4.7) yields
$$
g(n) = \Theta\left(\sum^{\log_b n – 1}_{j = 0} a^j \left(\frac n {b^j}\right)^{\log_b a}\right) \;\;\;\;\; (4.9)
$$ We bound the summation within the $\Theta$ as in case 1, but this time we do
not obtain a geometric series. Instead, we discover that every term of the
summation is the same:
\begin{align}
\sum^{\log_b n – 1}_{j=0} a^j \left( \frac n {b^j}\right)^{\log_b a}
& = n^{\log_b a} \sum^{\log_b n – 1}_{j=0} \left(\frac a {b^{\log_b a}}\right)^j \\
& = n^{\log_b a} \sum^{\log_b n – 1}_{j=0} 1 \\
& = n^{\log_b a} \log_b n \\
\end{align}
Substituting this expression for the summation in equation (4.9) yields
\begin{align}
g(n)
& = \Theta\left(n^{\log_b a} \log_b n\right) \\
& = \Theta\left(n^{\log_b a} \lg n\right) , \\
\end{align}
and case 2 is proved.[…]
4.4.2 Floors and ceilings
To complete the proof of the master theorem, we must now extend our analysis to the situation in which floors and ceilings are used in the master recurrence, so that the recurrence is defined for all integers, not just exact powers of $b$.
[…] Lower bounding […] requires much the same technique as upper bounding […], so we shall only present this latter bound.[…]
We can now evaluate the summation
\begin{align}
g(n) = \sum^{\left\lfloor \log_b n \right\rfloor – 1}_{j=0} a^j f(n_j) \;\;\;\;\; (4.14)
\end{align}
from (4.13) in a manner analogous to the proof of Lemma 4.3.
[…]
For case 2, we have $f(n) = \Theta(n^{\log_ab})$. If we can show that
$f(n_j) = O(n^{\log_ba}/a^j) = O((n/b^j)^{\log_ba})$, then the proof for
case 2 of Lemma 4.3 will go through. [A proof of $f(n) = O\left(\frac {n^{\log_b a}} {a^j} \right)$ now follows.]
Thus, case 2 is proved.
Can anyone help me understand the last emphasized part?
Best Answer
When the authors write "the proof for case 2 of Lemma 4.3 will go through", they mean that statement $g(n) = O\left(n^{\log_b a} \lg n\right)$ can be proven from $f(n_j) = O((n/b^j)^{\log_ba})$ using a proof that is very similar to that for case 2 of Lemma 4.3.
Basically, that proof is the following: