2
$\begingroup$

In case 3 of the master theorem, which is applicable when most of the work is being done at the top node (roughly speaking), we also need a regularity condition that the work done at the topmost level is greater than that at the bottom levels, in addition to it being greater than work being done at last level. However, in case 1, which is applicable when most of the work is being done at the last level, we assume that it will be greater than all the previous levels. Why is that? Shouldn't there be a regularity condition for case 1 also?

$\endgroup$
  • 1
    $\begingroup$ Note that it's "the master theorem". It's not named after some guy called Professor Master. Also, please state explicitly what version of the theorem you're using. Different people write the theorem different ways and your "case 3" could easily be somebody else's "case b". $\endgroup$ – David Richerby Aug 27 '17 at 18:41
  • $\begingroup$ Questions of the form, "why is additional requirement X needed for proving Y?" are not always fruitful. The answer may just be, "because we couldn't make the proof work without it". There may be other proofs. $\endgroup$ – Raphael Aug 27 '17 at 20:26
  • $\begingroup$ @Raphael My answer addresses all these points. $\endgroup$ – Yuval Filmus Aug 27 '17 at 22:59
1
$\begingroup$

You are asking why the regularity condition is absent in case 1. What you should be asking instead is why the regularity condition is present in case 3. Let's start with the latter question.

Consider the recursion $$ T(n) = T(n/2) + f(n), \text{ where } f(n)=n^{1 + (\log_2 n \bmod 2)}. $$ For simplicity I define the function $f$ only for powers of 2, and it is given by $f(2^{2k}) = 2^{2k}$, $f(2^{2k+1}) = 2^{4k+2}$. You can check that $T(n) = \Theta(n^2)$, and so it is not the case that $T(n) = \Theta(f(n))$ (since for $n = 2^k$, $f(n) = n$).

This shows that some regularity condition is indeed necessary in case 3. The proof shows that this particular regularity condition suffices for the conclusion $T(n) = \Theta(f(n))$ to hold.

In case 1, in contrast, the proof works for every function $f(n)$ satisfying the condition $f(n) = O(n^c)$, where $c$ is strictly smaller than the critical exponent. You can try to concoct an example like the one above, but you will necessary fail, since the master theorem states that the condition $f(n) = O(n^c)$ suffices for the conclusion $T(n) = \Theta(n^{c_{crit}})$ to hold.

You can still ask whether there is some deeper reason that the regularity condition is needed in case 3 but not in case 1. I think that the example above is very suggestive: the reason is that in case 3 the answer involves $f(n)$, whereas in case 1 it doesn't. Therefore if $f(n)$ is not well-behaved then it could show up in case 3, but is irrelevant for case 1.

$\endgroup$

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.