1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Which edition of "Introduction to Algorithms of Cormen, Leiserson, Rivest, Stein (CLRS)"? $\endgroup$ – Apass.Jack Dec 28 '18 at 15:33
  • $\begingroup$ @Apass.Jack third edition $\endgroup$ – Mergasov Dec 28 '18 at 15:34
  • $\begingroup$ The proof should be very similar. $\endgroup$ – Yuval Filmus Dec 28 '18 at 15:47
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.