patternMinor
Conditions for applying Case 3 of Master theorem
Viewed 0 times
casemasterfortheoremconditionsapplying
Problem
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 $cn_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?
$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 $cn_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?
Solution
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 $c0$.
Proof. There exists some $n_0>0$ such that $af(\frac nb)\leq cf(n)$ and $0 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 $c0$.
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 $c0$.
Proof. There exists some $n_0>0$ such that $af(\frac nb)\leq cf(n)$ and $0 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 $c0$.
Context
StackExchange Computer Science Q#121735, answer score: 6
Revisions (0)
No revisions yet.