Conditions for applying Case 3 of Master theorem

Question

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?

Answer 1

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