Why does case 3 regularity condition of master theorem always hold when f(n)=$n^k$ and f(n)=$\Omega(n^{\lg_b^{a+\epsilon}})$

Question

I know that the regularity condition for master theorem Case#3 stating that [$af(\frac{n}{b}) ≤ cf(n)$ for some constant $c < 1$ and all sufficiently large n] always holds when the $f(n)=n^k$,$f(n)=\Omega(n^{\lg_b^{a+\epsilon}})$. However, I have tried to prove this statement, and was unable to do so.

The question is how to prove that the regularity condition of master theorem case 3 always holds on the two above-mentioned functions.

Answer 1

If $f(n) = n^k$, we know that $k > \log_ba$, since this is Case 3; this is the meaning of the second condition in your post. We have to find $c<1$ such that for large $n$, $$ a(n/b)^k < cn^k. $$ We can simply choose $c = a/b^k$. Since $k > \log_b a$, we get $c < 1$.

---

If all you know about $f$ is that is satisfies $f(n) = \Omega(n^{\log_ba+\epsilon})$ for some $\epsilon>0$, then you cannot conclude that $f$ is regular. Indeed, given $a,b,\epsilon$, take $$ f(n) = a^{\tfrac{1}{2} \lfloor \log_{b^2} n \rfloor(1+\epsilon/\log_ba)} $$ Then $$ f(n) > a^{\tfrac{1}{2}(\log_{b^2} n - 1)(1+\epsilon/\log_ba)} = \Omega(a^{\log_b n(1 + \epsilon/\log_b a)}) = \Omega(n^{\log_b a(1+\epsilon/\log_b a)}) = \Omega(n^{\log_b a+\epsilon}). $$ On the other hand, if $n = b^{2m+1}$ for integer $m$ then $f(n/b) = f(n)$, and in particular, no $c<1$ satisfies $af(n/b) \leq cf(n)$. Since $b^{2m+1}$ can be arbitrarily large, we conclude that $f$ is not regular.

Answer 2

In case of $f(n)=\Omega(n^{\log_b^{a+\epsilon}})$, we need to find $c<1$ such that for sufficiently large n

$a*\Omega((\frac{n}{b})^{\log_b^{a+\epsilon}})\leq c*\Omega(n^{\log_b^{a+\epsilon}})$

By slightly modifying the left part we obtain the following inequality

$\frac{a}{a+\epsilon}*\Omega(n^{\log_b^{a+\epsilon}})\leq c*\Omega(n^{\log_b^{a+\epsilon}})$

Thus we can take $c=\frac{a}{a+\epsilon}$ and here $c<1$ as $\epsilon>0$ according to case 3 of master theorem.

Important Note

This hypothesis has been shown to be wrong in the answer by Yuval Filmus. Regardless, I am keeping it, for anyone not to make a similar mistake.