Exercise 4.5.5

$\star$ Consider the regularity condition $af(n/b) \ge cf(n)$ for some constant $c < 1$, which is part of case 3 of the master theorem. Give an example of constants $a \ge 1$ and $b > 1$ and a function $f(n)$ that satisfies all the conditions in case 3 of the master theorem, except the regularity condition.

$$ a = 1 \\ b = 2 \\ f(n) = n(2-\cos{n}) $$

Thus, if we try to proove it:

$$ \frac{n}{2}(2 - \cos\frac{n}{2}) < cn \\ \frac{1 - cos(n/2)}{2} < c \\ c \ge 1 - \frac{cos(n/2)}{2} $$

Since $\min\cos(n/2) = -1$, this implies that $c \ge 3/2$. But $c < 1$.