Solving Recurrence relation with master method? I have to solve the following recurrence equation and I thought to solve it with case #3 of the master theorem. Can I do that?

$$T(1) = c&gt;0 $$
$$T(n) = 9T(n/3) + f(n)$$
$$f(n) = n^2\cdot lg^3 (n) + n^3 \cdot lg(n)$$

I think that $f(n) = \Omega(n^{log_ba})$ where $a=9, b=3$ so $n^{log_ba}=n^2$.

Since  $f(n) = n^3 lg(n)$, we can prove that $$a\cdot f(n/b) \leq c\cdot f(n)$$.

Is it a correct solution?

The only piece I am afraid could be tricky is proving $a\cdot f(n/b) \leq c\cdot f(n)$.

Thank you,
Alan
You are claiming that "we can prove that $af(n/b) \leq cf(n)$". There are two problems with this claim:


This is now what you actually need in order to apply the master theorem. The master theorem needs you to show that there exists $c &lt; 1$ for which $af(n/b) \leq c f(n)$ for all large enough $n$.
You haven't proved your claim.


Reiterating, to prove the claim you need to come up with a value of $c &lt; 1$ such that the following inequality holds for large enough $n$:
$$
9 (n/3)^3  \log(n/3) \leq cn^3 \log n.
$$
This holds for $c = 1/3$, since
$$
9(n/3)^3 \log(n/3) &lt; 9(n/3)^3 \log n = \frac{1}{3} n^3 \log n.
$$