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

If all you know about $f$ is that is satisfies $f(n) = \Omega(n^{\log_ba+\epsilon})$ for some $\epsilon&gt;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) &gt; 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&lt;1$ satisfies $af(n/b) \leq cf(n)$. Since $b^{2m+1}$ can be arbitrarily large, we conclude that $f$ is not regular.