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.