Missing part of the proof of Master Theorem's case 2 (with ceilings and floors) in CLRS?

Question

I am trying to go through the proof of the Master Theorem in Introduction to Algorithms of Cormen, Leiserson, Rivest, Stein (CLRS). The theorem providers an asymptotic analysis for recurrence relations $T(n)=aT(n/b)+f(n)$ where $a\geq 1, b > 1$ and $f(n)$ is an asymptotically positive function.

The authors create a formulation of the following lemma (4.3):

2. if $f(n) = \Theta(n^{\log_ba})$, then $g(n)=\Theta(n^{\log_ba}{\log_bn})$

where $g(n) = \sum_{j=0}^{\lfloor \log_b n \rfloor - 1} a^jf(n_j)$ and $n_j = \begin{cases} n, & \text{if j = 0} \\ \lceil n_{j-1}/b \rceil, & \text{if j > 0} \end{cases}$

When it is proving for the situation in which floors and ceilings appear the autrors make a statement:

For case 2, we have $f(n)=\Theta(n^{\log_b a})$. 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.

Well, I got it. When this condition is true we can find some constant $c$, such that

$g(n) \le c\sum_{j=0}^{\lfloor \log_b n \rfloor - 1} n^{\log_b a}$

and conclude that $g(n) = O(n^{\log_b a}{\log_bn})$.

But it's not a proof that $g(n) = \Omega(n^{\log_b a}{\log_bn})$. Where is one? Should it be obvious? How can I prove this statement?

Answer 1

As you said, the book does not include a proof for $g(n) = \Omega(n^{\log_b a}{\log_bn})$. There is no need to.

Recall that part of proof is to show the upper bound of $f(n)$, when $f(n)$ is defined by the following recurrence relation using the ceiling function, which is the formula 4.25 in CLRS. $$T(n) = aT(\lceil\frac nb\rceil) + f(n)$$ Noting that the lower bound for $T(n)$ "is routine, since we can push through the bound $\lceil\frac nb\rceil\ge\frac nb$", the book proceed to prove an upper bound for the above $T(n)$, where we only need to show an upper bound for $g(n)$.

---

What you meant might be the corresponding situation in the case when $f(n)$ is defined using the floor function as the formula 4.26 in CLRS, $$T(n) = aT(\lfloor\frac nb\rfloor) + f(n)$$ in which case, we will defined $h(n) = \sum_{j=0}^{\lfloor \log_b n \rfloor-1} a^jf(n_j)$ and $n_j = \begin{cases} n, & \text{if j = 0} \\ \lfloor n_{j-1}/b \rfloor, & \text{if j > 0} \end{cases}$.

Note that the definition of $h(n)$ is not the same as that of $g(n)$, although the two are almost the same.

I will leave as an exercise for you to prove a lower bound for the above $T(n)$ using $h(n)$. In particular, you will need to show that in case 2, i.e., when $f(n)=\Theta(n^{\log_b a})$, $$h(n) = \Omega(n^{\log_b a}{\log_bn}).$$

Hint, as said in the last statement of section 4.6.2 and by Yuval's comment, the proof of the lower bounds is similar.