There already are many questions and answers about the importance of the regularity condition in case 3 of the Master Theorem. My question is about when can we safely assume the regularity condition is satisfied when f is only provided as a $\Theta(g(n))$, which is actually what happens most of the time when we don't want to bother detailing the exact expression for $f$.
From my understanding, I believe that nothing can be assumed without additional information on f. In the example provided on wikipedia of $T(n) = T\left(\frac{n}{2}\right) + n(2 - \cos{n})$ we have $f(n) = \Theta(n)$ since $(2 - \cos{n}) \in [1, 3]$. Yet $f$ does not satisfy the regularity condition and we therefore cannot deduce that that $T(n) = \Theta(n)$.
Going down the definition of $f(n) = \Theta(g(n))$, we have $n_0 \geq 0$, $c_0 > 0$ and $c_1 > 0$ such that for every $n \geq n_0$ $c_0 g(n) \leq f(n) \leq c_1 g(n)$. Let's assume $g(n) = n^c$.
Given a Master Theorem instance of $T(n) = aT\left(\frac{n}{b}\right) + \Theta(n^c)$, we are in case 3 of the Master Theorem when we have $a < b^c$. Now to check the regularity condition we need to check that $a f\left(\frac{n}{b}\right) \leq kf(n)$ for some $k < 1$. We therefore have that for $n \geq n_0$ $$ \begin{aligned} af\left(\frac{n}{b}\right) &\leq a c_1 g\left(\frac{n}{b}\right)\\ &\leq a c_1 \frac{n^c}{b^c} \end{aligned} $$ and $$ \begin{aligned} kf(n) &\geq k c_0 g(n)\\ &\geq k c_0 n^c \end{aligned} $$ assuming $n > 0$, we therefore need that $$ \begin{aligned} k c_0 &\geq \frac{a c_1}{b^c}\\ k &\geq \frac{c_1}{c_0}\frac{a}{b^c}\\ \end{aligned} $$
In the Wikipedia example, we have $\frac{c_1}{c_0} = 3$ and $\frac{a}{b^c} = \frac{1}{2}$. We would therefore need that $k \geq \frac{3}{2}$ which contradicts $k < 1$.
Now when $f$ just comes out of a loop intrication without inner tests that would make the worst and best cases different, $f$ is a polynomial, and we just use its dominant power as a $\Theta$. I believe what saves us is that we can choose the $n_0$ in the Landau notation, and by increasing it we can have $\frac{c_1}{c_0} < \epsilon$ for any $\epsilon > 1$. And since $\frac{a}{b^c} < 1$, we can always find some $n_0$ such that for any $n \geq n_0$, the regularity condition is satisfied.
Is this sound ? Can we use the generalized Akra-Bazzi Theorem to just not bother ?
