Pergunta

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

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top