2
$\begingroup$

In Introduction to Algorithms, Lemma 4.4 of the proof of the master theorem goes like this. $a\geq1$, $b>1$, $f$ is a nonnegative function defined on exact powers of b. The recurrence relation for $T$ is $T(n) = a T(n/b) + f(n)$ for $n=b^i$, $i>0$.

For the third case, we have $f(n) = \Omega(n^{\log_ba +\epsilon})$ for some fixed $\epsilon>0$ and that $ af(n/b)\leq cf(n)$ for fixed $c<1$ and for all sufficiently large $n$. In this case, $T(n) =\Theta(f(n))$ since $f(n) = \Omega(n^{\log_ba +\epsilon})$.

I was wondering if the condition that $f(n) = \Omega(n^{\log_ba +\epsilon})$ is unnecessary since the regularity condition $ af(n/b)\leq cf(n)$ for all $n>n_0$ for fixed $c<1$ and for some $n_0$ implies that $$ \begin{align*} f(n)&\geq m\left(\frac{a}{c}\right)^{\log_b(n/n_0)} \text{ where } m=\min_{1\leq x\leq n_0}{f(x)}\\&\ge\left(\frac{n}{n_0}\right)^{\log_b(a/c)}=\Theta(n^{\log_ba +\log_b(c^{-1})})=\Theta(n^{\log_ba +\epsilon}). \end{align*} $$ This will hold as long as $f(n)$ is non-zero. Hence $f(n)=\Omega(n^{\log_ba +\epsilon})$. Therefore we merely need to add the condition that $f(n)$ is positive for all but finitely many values of $n$ for case 3. Am I correct about this?

$\endgroup$
3
  • 2
    $\begingroup$ You seem to be right. Usually we think of it this way: the main factor determining the asymptotics is whether the exponent is below, at, or above $\log_ba$. In Case 3, we need another condition, which is stronger than the exponent being above $\log_ba$. $\endgroup$ – Yuval Filmus Mar 13 '20 at 18:23
  • $\begingroup$ It would have been more accurate for me to say that $f(n)$ is positive for the base cases, such that $m = min_{1\leq x\leq n_0} f(x)$ is positive. Since if m=0, $f(n)$ can be of any size (even if positive). $\endgroup$ – Jia Cheng Sun Mar 14 '20 at 1:37
  • $\begingroup$ I've just realised that this question is precisely stated in exercise 4.6-3 that directly follows the chapter in CLRS. $\endgroup$ – Jia Cheng Sun Jun 27 '20 at 9:11
5
$\begingroup$

Yes, your sharp observation is completely correct.


To be compatible with the highly strict style shown at section 4.6, Proof of the master theorem of Introduction to Algorithms, here is the complete proposition and a slightly more rigorous proof. It seems that the proof in the question ignores the requirement that $f$ is defined only on exact powers of $b$.

(Regularity implies lower-bounded by a greater-exponent polynomial.) Let $a\geq1$, $b>1$ and $f$ be a nonnegative function defined on exact powers of $b$. Suppose $af(\frac nb)\leq cf(n)$ for some fixed $c<1$ and for all sufficiently large $n$. Furthermore, $0 < f(n)$ for all sufficiently large $n$. Then $f(n) = \Omega(n^{log_ba +\epsilon})$ for some fixed $\epsilon>0$.

Proof. There exists some $n_0>0$ such that $af(\frac nb)\leq cf(n)$ and $0 < f(n)$ for all $n\ge n_0$. We can assume $n_0$ is an exact power of $b$ since, otherwise, we can replace $n_0$ by $b^{\lceil\log_b{n_0}\rceil}$.

Let $n\ge n_0$ be an exact power of $b$. So $n = n_0b^m$, where $m=\log_b\frac n{n_0}$ is an integer since both $n$ and $n_0$ are exact powers of $b$. Applying $af(k/b)\leq cf(k)$ multiple times, we get

$$f(n) \ge \frac acf(\frac nb) \ge (\frac ac)^2f(\frac n{b^2})\ge \cdots \ge (\frac ac)^mf(\frac n{b^m})=(\frac ac)^mf(n_0)$$

Since $$(\frac ac)^m=(\frac ac)^{\log_b\frac n{n_0}} =(\frac n{n_0})^{\log_b\frac ac}=(\frac n{n_0})^{\log_ba-\log_bc}=c_0n^{log_ba+\epsilon}$$ where $\epsilon=-\log_bc > 0$ and $c_0=(\frac1{n_0})^{log_ba +\epsilon}$ are two constants, we have

$$f(n) \ge c_0f(n_0)n^{log_ba +\epsilon}.$$ So, $$f(n)=\Omega(n^{log_ba +\epsilon}).\quad \checkmark$$


What happens if $n$ is not necessarily an exact power of b? The same result will hold if we replace $\frac nb$ by $\lfloor \frac nb\rfloor$ or $\lceil \frac nb\rceil$. The following is a version when $\lfloor \frac nb\rfloor$ is used.

Let $a\ge1$, $b>1$ and $f$ be a nonnegative function defined on positive integers. Suppose $af(\lfloor \frac nb\rfloor)\leq cf(n)$ for some fixed $c<1$ and for all sufficiently large $n$. Furthermore, $0 < f(n)$ for all sufficiently large $n$. Then $f(n) = \Omega(n^{log_ba +\epsilon})$ for some fixed $\epsilon>0$.

$\endgroup$
4
  • $\begingroup$ If n is not an exact power of b, can we still prove the same result? $\endgroup$ – jinge Nov 15 '20 at 4:16
  • $\begingroup$ @jinge, if n is not an exact power of b, how should we define n/b such as 7/3? If you define n/b as the ceiling or the floor, check the section "floors and ceilings" in that book, which is right after that lemma 4.4. $\endgroup$ – John L. Nov 15 '20 at 18:10
  • $\begingroup$ Yes, I know the section in that book. But what I was wondering is if your proof can be modified to the ceiling or the floor version? $\endgroup$ – jinge Nov 16 '20 at 7:08
  • $\begingroup$ @jinge, please check my updated answer. $\endgroup$ – John L. Nov 18 '20 at 4:35

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.