Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
It would help if you told us what the "master theorem" says. –  Chris Godsil Feb 13 '13 at 13:05
    
@ChrisGodsil: link to it added. –  aplavin Feb 13 '13 at 13:30
    
Why do you think $f$ is not regular? We have $af(n/b) \leq (5/9) f(n)$. –  Marek Feb 13 '13 at 14:07
    
@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$. –  aplavin Feb 13 '13 at 14:21
    
@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)$. –  Marek Feb 13 '13 at 14:31
show 3 more comments

1 Answer 1

up vote 2 down vote accepted

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).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.