Regularity condition in the master Theorem in the presence of Landau notation for f 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 &gt; 0$ and $c_1 &gt; 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 &lt; 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 &lt; 1$. We therefore have that for $n \geq n_0$
$$
  \begin{aligned}
    af\left(\frac{n}{b}\right) 
      &amp;\leq a c_1 g\left(\frac{n}{b}\right)\\
      &amp;\leq a c_1 \frac{n^c}{b^c}
  \end{aligned}
$$
and
$$
  \begin{aligned}
    kf(n) 
      &amp;\geq k c_0 g(n)\\
      &amp;\geq k c_0 n^c
  \end{aligned}
$$
assuming $n &gt; 0$, we therefore need that
$$
  \begin{aligned}
    k c_0 &amp;\geq \frac{a c_1}{b^c}\\
    k &amp;\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 &lt; 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} &lt; \epsilon$ for any $\epsilon &gt; 1$. And since $\frac{a}{b^c} &lt; 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 ?
Suppose that $T(n) = aT(n/b) + \Theta(f(n))$. What this means is that $T(n) = aT(n/b) + g(n)$, where $g(n) = \Theta(f(n))$, say $c_{LB} f(n) \leq g(n) \leq c_{UB} f(n)$. Consider now the following two recurrences:
$$
T_{LB}(n) = aT_{LB}(n/b) + c_{LB} f(n), \\
T_{UB}(n) = aT_{UB}(n/b) + c_{UB} f(n),
$$
with the same initial conditions as the initial recurrence. You can show inductively that $T_{LB}(n) \leq T(n) \leq T_{UB}(n)$. Assuming that the function $f(n)$ does satisfy the regularity conditions, you can use the master theorem to solve the two auxiliary recurrences, and hence to deduce the solution to the original recurrence.