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?


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)$

enter image description here

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.

  • $\begingroup$ Looks good! One little caveat: the Master theorem assumes that $n=b^k$, i.e. here $n=2^k$ (for better or worse). That is you would check the regularity condition only for such $n$; is it violated there, too? $\endgroup$ – Raphael Aug 8 '14 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.