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$ Commented Feb 13, 2013 at 13:05
  • $\begingroup$ @ChrisGodsil: link to it added. $\endgroup$
    – aplavin
    Commented 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
    Commented 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
    Commented 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
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .