2
$\begingroup$

I know that the regularity condition for master theorem Case#3 stating that [$af(\frac{n}{b}) ≤ cf(n)$ for some constant $c < 1$ and all sufficiently large n] always holds when the $f(n)=n^k$,$f(n)=\Omega(n^{\lg_b^{a+\epsilon}})$. However, I have tried to prove this statement, and was unable to do so.

The question is how to prove that the regularity condition of master theorem case 3 always holds on the two above-mentioned functions.

$\endgroup$
2
$\begingroup$

If $f(n) = n^k$, we know that $k > \log_ba$, since this is Case 3; this is the meaning of the second condition in your post. We have to find $c<1$ such that for large $n$, $$ a(n/b)^k < cn^k. $$ We can simply choose $c = a/b^k$. Since $k > \log_b a$, we get $c < 1$.


If all you know about $f$ is that is satisfies $f(n) = \Omega(n^{\log_ba+\epsilon})$ for some $\epsilon>0$, then you cannot conclude that $f$ is regular. Indeed, given $a,b,\epsilon$, take $$ f(n) = a^{\tfrac{1}{2} \lfloor \log_{b^2} n \rfloor(1+\epsilon/\log_ba)} $$ Then $$ f(n) > a^{\tfrac{1}{2}(\log_{b^2} n - 1)(1+\epsilon/\log_ba)} = \Omega(a^{\log_b n(1 + \epsilon/\log_b a)}) = \Omega(n^{\log_b a(1+\epsilon/\log_b a)}) = \Omega(n^{\log_b a+\epsilon}). $$ On the other hand, if $n = b^{2m+1}$ for integer $m$ then $f(n/b) = f(n)$, and in particular, no $c<1$ satisfies $af(n/b) \leq cf(n)$. Since $b^{2m+1}$ can be arbitrarily large, we conclude that $f$ is not regular.

$\endgroup$
2
  • $\begingroup$ An amazing construction! But I still have two questions. (1) If we don't use rounding operation, can we still construct a function f(n) that break the regularity? (2) Does such a constructed function indeed fail to apply the master theorem? $\endgroup$ – jinge Nov 15 '20 at 4:46
  • $\begingroup$ (1) It depends what you allow me to use. For example, if you only allow me to use polynomial functions, then it is impossible. (2) The master theorem requires the regularity condition, and indeed, there are non-regular examples in which the conclusion of the theorem fails, perhaps even this one. $\endgroup$ – Yuval Filmus Nov 15 '20 at 6:53
0
$\begingroup$

In case of $f(n)=\Omega(n^{\log_b^{a+\epsilon}})$, we need to find $c<1$ such that for sufficiently large n

$a*\Omega((\frac{n}{b})^{\log_b^{a+\epsilon}})\leq c*\Omega(n^{\log_b^{a+\epsilon}})$

By slightly modifying the left part we obtain the following inequality

$\frac{a}{a+\epsilon}*\Omega(n^{\log_b^{a+\epsilon}})\leq c*\Omega(n^{\log_b^{a+\epsilon}})$

Thus we can take $c=\frac{a}{a+\epsilon}$ and here $c<1$ as $\epsilon>0$ according to case 3 of master theorem.

Important Note

This hypothesis has been shown to be wrong in the answer by Yuval Filmus. Regardless, I am keeping it, for anyone not to make a similar mistake.

$\endgroup$
1
  • 1
    $\begingroup$ If all you know is that $f(n) = \Omega(n^{\log_ba+\epsilon})$, you cannot conclude that $f$ is regular. For example, suppose that $a=b=2$, and consider $f(n) = 16^{\lfloor \log_4n \rfloor} = \Omega(n^2)$. If $n=2\cdot 4^m$ for integer $m$ then $2f(n/2) = 2f(n)$, and in particular there is no $c<1$ such that for all large enough $n$, we have $2f(n/2)\leq cf(n)$. $\endgroup$ – Yuval Filmus Sep 17 '20 at 20:17

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.