Solving Recurrence relation with master method?

Question

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

Answer 1

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

1. 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 < 1$ for which $af(n/b) \leq c f(n)$ for all large enough $n$.

2. You haven't proved your claim.

Reiterating, to prove the claim you need to come up with a value of $c < 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) < 9(n/3)^3 \log n = \frac{1}{3} n^3 \log n. $$