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$ Mar 13, 2020 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$ Mar 14, 2020 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$ Jun 27, 2020 at 9:11

1 Answer 1

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, 2020 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, 2020 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, 2020 at 7:08
  • $\begingroup$ @jinge, please check my updated answer. $\endgroup$
    – John L.
    Nov 18, 2020 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.