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?
$\begingroup$
$\endgroup$
3
-
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 RicherbyCommented Aug 27, 2017 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$– RaphaelCommented Aug 27, 2017 at 20:26
-
$\begingroup$ @Raphael My answer addresses all these points. $\endgroup$– Yuval FilmusCommented Aug 27, 2017 at 22:59
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Aug 27, 2017 at 12:47