Issue while applying Master Theorem

Question

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

Answer 1

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