4
$\begingroup$

I've read about the master theorem for solving recurrences in Introduction to Algorithms, but have a problem (probably, due to misunderstanding) while applying it in some cases. For example, having recurrence $T(n) = 5 T(\frac{n}{3}) + \Theta(n^2 \log n)$ and trying to apply this theorem I have: $a=5; b=3; f(n)=\Theta(n^2 \log n)$. So, the third case ($f(n)=\Omega(n^{\log_b a + \varepsilon})$) of the theorem seems to be suitable, if $f(n)$ is regular (i.e. $a f(\frac{n}{b}) \leq c f(n), c < 1$). But as I understand, $f(n) = \Theta(n^2 \log n)$ doesn't imply regularity of $f(n)$ and the master theorem is impossible to apply in this case. Do I understand right?

P.S.: The master theorem itself is stated for example in http://www.csail.mit.edu/~thies/6.046-web/master.pdf

$\endgroup$
8
  • $\begingroup$ It would help if you told us what the "master theorem" says. $\endgroup$ Feb 13, 2013 at 13:05
  • $\begingroup$ @ChrisGodsil: link to it added. $\endgroup$
    – aplavin
    Feb 13, 2013 at 13:30
  • $\begingroup$ Why do you think $f$ is not regular? We have $af(n/b) \leq (5/9) f(n)$. $\endgroup$
    – Marek
    Feb 13, 2013 at 14:07
  • $\begingroup$ @Marek: why do we have this? $f(n)=\Theta(n^2 \log n)$ doesn't mean that $f(n)=c\cdot n^2 \log n$. $\endgroup$
    – aplavin
    Feb 13, 2013 at 14:21
  • $\begingroup$ @chersanya: that's true of course, but the additional terms can't spoil the asymptotic behavior (the regularity only needs to hold for $n$ big enough, not for all $n$). So when $n$ is big enough, it's okay (and this can be made rigorous) to assume that $f(n)$ actually is $C n^2 \log(n)$. $\endgroup$
    – Marek
    Feb 13, 2013 at 14:31

1 Answer 1

2
$\begingroup$

Assuming the facts given in the question, for $n$ big enough we have $k_1 g(n) \leq f(n) \leq k_2 g(n)$ where $g(n) = n^2 \log n$. Because $g(n)$ is regular, we can apply the master theorem to it and it gives us the same result for both $k_1 g(n)$ and $k_2 g(n)$. Since $f(n)$ is bounded between the two functions, we get the master result by sandwiching. Therefore in case 3 for $f(n) = \Theta g(n)$ with $g(n)$ regular we can as well assume $f(n) = g(n)$.

The problems can only occur in case 2 because of the delicate interplay of the merging and the recursion (which are both effects of the same order).

$\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.