Regularity condition for cases 1 & 2

Question

My question concerns the version of the Master Theorem described in CLRS and in this handout.

I already understand the following:

• If the regularity condition in case 3 does not hold, then we can't apply case 3.
• If the regularity condition in case 3 holds then $f(n)=\Omega(n^{\log_ba\ +\ \epsilon})$ is definitely true.

I have two questions:

• Can there be a situation where $f(n)=\Omega(n^{\log_ba\ +\ \epsilon})$ is true but the regularity condition does not hold?
• Why isn't there a regularity condition for cases 1 and 2? Is there a proof that a similar condition is unnecessary (or at least what is the intuition for it being unnecessary in cases 1 and 2)?

Answer 1

Can there be a situation where $f(n)=\Omega(n^{\log_b a + \varepsilon})$ is true but the regularity condition does not hold?

Yes. Let $f(n)$ be equal to $n$ if $n$ is between an even power of two and the next (odd) power of two, and $2n$ otherwise. Formally:

$ f(n)= \begin{cases} n &\mbox{if } \exists k \in \mathbb{N} : 2^{2k} \le n < 2^{2k+1}; \\ 2n &\mbox{otherwise}. \end{cases} $

Consider the recurrence $T(n)=T(n/2)+ f(n)$. In this case $a=1, b=2$, and $n^{\log_b a + \varepsilon} = n^\varepsilon$. You can see that, for $\varepsilon<1$, $f(n) \ge n = \Omega(n^\varepsilon)$.

Nevertheless the regularity condition is not satisfied. Indeed, for any choice of $c<1$ and $n_0 \ge 0$, you can pick $n= 2^{2k}$ for some sufficiently large integer value of $k \ge 1$ that satisfies $2^{2k} \ge n_0$.

Then $f(n)=n$ while $n/b = n^{2k-1}$ is an odd power of $2$, hence $a f(n/b)=2 \cdot (n/2) = n$. This shows that $a f(n/b) = n = f(n)$ and therefore we cannot have $a f(n/b) < c f(n)$.

Why isn't there a regularity condition for cases 1 and 2? Is there a proof that a similar condition is unnecessary...

Yes. The proof you are looking for is exactly the standard proof of cases 1 and 2 in the master Theorem (which does not require the regularity condition).

Answer 2

First, let's discuss the meaning of the regularity condition. It states that $af(n/b)<=cf(n)$ for a constant $c < 1$ and $n > n_0$. Now consider the recurrence equation $T(n) = aT(n/b) + f(n)$. The corresponding recursion tre has $f(n)$ as its root node, and $a$ children each one doing $f(n/b)$ work. In case three of the master theorem the cost of the tree is dominated by the cost of its root node, and this corresponds to a geometric series with decreasing terms. In case one the cost of the tree is dominated by the cost of its leaves and this corresponds to a geometric series, with increasing terms. Finally, in case 2 the cost of the tree is evenly distributed among the levels of the tree.

Therefore, in case one the work done in the root node is less than the work done by its children, and in case two it is equal.

Now note that the conditions associated to cases one and two are already enough to assure that the work done in the root node is less than the work done by its children ($f(n)=O\left(n^{\log _{b} a-\epsilon}\right)$ for $\epsilon > 0$), and in case two it is equal ($f(n)=\Theta\left(n^{\log _{b} a}\right)$). No additional conditions are required: indeed, no additional assumptions are in the master theorem for cases one and two.

What about case three? The associated condition ($f(n)=\Omega\left(n^{\log _{b} a+\epsilon}\right)$ for $\epsilon > 0$) is not enough to guarantee that the work done in the root node is greater than the work done by its children, and this is why we also need the regularity condition. Here is an example, answering your question, in which the condition holds, but the regularity condition does not:$T(n) = T(n/2) + n (\sin(n - \pi/2) + 2)$. Indeed, for $f(n) = n (\sin(n - \pi/2) + 2)$ there is at least a value $x$ such that $f(x/2) > f(x)$ (actually many such $x$ exist), but $f(n) \geq n \ \forall n$.