Consider a recurrence of the form
$T(n) = a T(n/b) + f(n)$
Master theorem's regularity condition excludes some cases (for example, when $f(n)$ is oscillating).
Suppose, however, that $f(n)$ is always less than or equal to a function $g(n)$ that does not violate the regularity condition, so that the master theorem is applicable if $g(n)$ is used instead of $f(n)$. Consider then the following recurrence:
$T'(n) = a T'(n/b) + g(n)$
and assume that the master theorem gives the solution $T'(n)=\Theta(g(n))$.
My doubt is this: can I then safely conclude that $T(n)=O(g(n))$?
In other words, can I be sure that the solution of a recurrence with a term replaced by its upper bound is an upper bound of the solution of the original occurrence? After all, the recurrence establishes a relationship between $T(n)$ and $T(n/b)$ but says nothing about what happens between $n/b$ and $n$ (and $f(n)$ here is oscillating...).