# 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 > 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 ?

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.