Consider the regularity condition $$af(n/b) \leq cf(n)$$ for some constant $$c < 1$$, which is part of case 3 of the master theorem. Give an example of constants $$a \geq 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.

Let’s get the simplest part of this exercise out of our way.

Picking the values for the constants.

Let’s pick $$a = 1$$, $$b = 2$$, and $$\epsilon = 1$$.

Now we need to find a function $$f(n)$$ such that $$f(n) = \Omega(n^{\log_b a+\epsilon}) = \Omega(n)$$

So, $$f(n)$$ is a function that is asymptotically larger than $$n$$, but fails to satisfy the regularity condition.

#### What does that mean

The regularity condition for the example values we chose:

$f(n/2) \leq cf(n)$

for some constant $$c < 1$$ and $$n$$ is sufficiently large.

This means we cannot choose any monotonically increasing function, as for such functions usually we can show that $$f(n/2) \leq f(n)/2$$, or in other words the regularity condition will hold with $$c = 1/2$$.

This is a hint that we need to look into functions that changes direction, like trigonometric functions.

$$f(n) = n \cos n$$ is a good example.

To make it $$\Omega(n)$$, we can use $$f(n) = 2n - n \cos n$$, so that it is never less than $$n$$.

#### Regularity Condition

We also have to show that regularity condition does not hold for this.

If regularity condition was satisfied for the $$f(n)$$ we chose,

\begin{aligned} f(n/2) &\leq cf(n) \\ 2 \cdot \frac n 2 - \frac n 2 \cdot \cos (n/2) &\leq c(2n - n \cos n) \\ 2 - \cos (n/2) &\leq 2c(2 - \cos n) \\ 2 - \cos (n/2) &\leq c(4 - 2\cos n) \\ \frac {2 - \cos (n/2)} {4 - 2\cos n} &\leq c \end{aligned}

If we have $$n \approx 2\pi$$, for example, $$n = 6$$,

\begin{aligned} \cos n &\approx 1 \\ \cos (n/2) &\approx -1 \end{aligned}

So, to satisfy the regularity condition we need,

\begin{aligned} c &\geq \frac {2 - \cos (n/2)} {4 - 2\cos n} \\ c &\geq \frac {2 - (-1)} {4 - 2 \cdot 1} \\ c &\geq \frac 3 2 \\ \end{aligned}

But this is in violation of $$c < 1$$

And this will happen for any $$n = 2k\pi$$, for some $$k \in \N$$.

In other words even for sufficiently large $$n$$, we cannot have $$c < 1$$ to satisfy the regularity condition for this example function.