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.