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

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):

1. 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?

• Which edition of "Introduction to Algorithms of Cormen, Leiserson, Rivest, Stein (CLRS)"? Dec 28, 2018 at 15:33
• @Apass.Jack third edition Dec 28, 2018 at 15:34
• The proof should be very similar. Dec 28, 2018 at 15:47
• – D.W.
Jul 5, 2021 at 6:14

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}).$$