15
$\begingroup$

I have been reading Introduction to Algorithms by Cormen et al. and I'm reading the statement of the Master theorem starting on page 73. In case 3 there is also a regularity condition that needs to be satisfied to use the theorem:

... 3. If

$\qquad \displaystyle f(n) = \Omega(n^{\log_b a + \varepsilon})$

for some constant $\varepsilon > 0$ and if

$\qquad \displaystyle af(n/b) \leq cf(n)$      [this is the regularity condition]

for some constant $c < 1$ and for all sufficiently large $n$, then ..

Can someone tell me why the regularity condition is needed? How does the theorem fail if the condition is not satisfied?

$\endgroup$

migrated from stackoverflow.com Oct 3 '12 at 16:54

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ can you write what the case is and what is the regulatory condition? $\endgroup$ – Nishant Oct 2 '12 at 4:10
  • 3
    $\begingroup$ I don't have a definitive answer for you, but it seems like if the regularity condition doesn't hold, then the subproblems take more and more time the smaller they are, so you get infinite complexity. $\endgroup$ – Vaughn Cato Oct 2 '12 at 4:14
  • $\begingroup$ I'm not sure that the regularity condition is necessary for the conclusion of the theorem to hold, but I think it's necessary for the proof used. With the regularity condition you have a rather straightforward proof, without, it would at least be hairy. $\endgroup$ – Daniel Fischer Oct 2 '12 at 22:28
  • $\begingroup$ copy on Theoretical Computer Science $\endgroup$ – Kaveh Oct 3 '12 at 19:16
10
$\begingroup$

Not a rigorous proof, but a "from the top of my head" explanation.

Imagine the recurrence $aT(n/b)+f(n)$ as a tree. The third case covers the scenario when the root node dominates the running time asymptotically, i.e. most of the work is being done in measly node on top of the recurrence tree. Then the running time is $\Theta(f(n))$.

To make sure the root actually does more work you need the

$a f(n/b) \leq cf(n)$.

This says that $f(n)$ (the amount of work done in the root) needs to be at least as big as the sum of the work done in the lower levels. (The recurrence is called $a$ times on $n/b$ of the input.)

E.g. for the recurrence $T(n)=2T(n/4)+n$ the work on the level below the root is one fourth as big and only done twice $(n/4+n/4)$ versus $n$ so the root dominates.

But what if the function didn't fulfill the regularity condition? E.g. $\cos(n)$ instead of $n$? Then the work done on the lower levels might be bigger than the work done in the root so you are not certain that the root dominates.

$\endgroup$
  • 3
    $\begingroup$ I used nicer formatting for your math text. You can click the "edited" link and see what I did. $\endgroup$ – Juho Oct 3 '12 at 20:33
7
$\begingroup$

Let $a = 1$ and $b = 2$, so that $$ T(2^n) = \sum_{k=0}^n f(2^k). $$ For case 3 to apply, we need $f(n) = \Omega(n^\epsilon)$ (for some $\epsilon > 0$) and the regularity condition, $f(n/2) \leq (1-\delta) f(n)$ (for some $\delta > 0$). You get the regularity condition from the proof, i.e. it's a proof-generated concept. While the regularity condition isn't necessary (consider the example given on Wikipedia, $f(n) = n(2-\cos n)$), you can't drop it completely, as the following example demonstrates. Consider $$f(2^n) = 2^{2^{\lfloor \log_2 n \rfloor}} > 2^{2^{\log_2n-1}} = 2^{n/2}.$$ Let $n = 2^{m+1}-1$. Then $$T(2^n) = \sum_{k=0}^m \sum_{t=2^k}^{2^{k+1}-1} 2^{2^k} = \sum_{k=0}^m 2^{2^k+k} = \Theta(2^{2^m+m}), \quad f(2^n) = 2^{2^m}. $$ So it's not true that $T(2^n) = \Theta(f(2^n))$.

There is a more general theorem, Akra-Bazzi, in which the regularity condition is replaced by an explicit quantity that comes into the result.

$\endgroup$
  • $\begingroup$ Sorry for resuming this old answer. Could you clarify why your function f violates the regularity condition? $\endgroup$ – Maiaux May 14 at 21:15
  • $\begingroup$ Sometimes $f(n/2) = f(n)$. $\endgroup$ – Yuval Filmus May 14 at 21:43

Your Answer

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