Satisfying all the conditions of case 3 of the Master Method except the regularity condition

Question

The regularity condition of case 3 of Master Method says that $af(n/b) < cf(n)$, for $c < 1$.

How to devise a recurrence relation that satisfies all other conditions of case 3 except the regularity condition?

Answer 1

For a run-time recurrence to satisfy all conditions of case 3 and not satisfy the regularity condition, we have to think of such $f(n)$ that grows or shrinks by a factor of $a$ when $n$ is decreased to $n/b$. Consider the following function:

$T(n) = T(n/2) + n(\sin(n - \pi/2) + 2)$

Let's take a look at $f(n)$

We can choose x such that $f(x/2) > f(x)$ even though $f(x) \geq x$ throughout. Let's check the regularity condition for $T(n) = T(n/2) + n(\sin(n - \pi/2) + 2)$

$(n/2)(\sin(n/2 - \pi/2) + 2) \leq cn(\sin(n - \pi/2) + 2)$

Thus $c \geq (1/2)\left(\frac{\sin(n/2 - \pi/2) + 2}{\sin(n - \pi/2) + 2}\right)$

Let $n = 2\pi k$, where k is odd

Then, $\sin(n/2 - \pi/2) + 2 = \sin(\pi/2) = 1$

$\sin(n - \pi/2) + 2 = \sin(-\pi/2) = -1$

And we get,

$c \geq (1/2)\left(\frac{1 + 2}{-1 + 2}\right)$

$\implies c \geq 3/2$ Thus we cannot choose c < 1 to satisfy the regularity condition.