I'm trying to solve this recurrance relation problem yet I cant seem to find an upper bound.
$$ T(n)=2T(\frac{n}{3})+nlog^2(n) $$
using the tree method I've got to $O(nlog^2(n))$, using the recursion calculation method, I've got $O(nlog^3(n)$
In either methods I'm not 100% certain of the steps I did, so to my assumption both my answers are wrong.
Any help would do alot.
Thanks!
taking $n = 3^m$ and considering $\log\equiv\log_3$ we have
$$ T(3^m)=2T(3^{m-1})+3^m m^2 $$
calling now $\mathcal{T}(\cdot)=T(3^{(\cdot)})$ we follow with
$$ \mathcal{T}(m)=2\mathcal{T}(m-1)+3^m m^2 $$
The homogeneous has the solution $\mathcal{T}_h(m)=2^m c_0$ and making now $\mathcal{T}_p(m)=2^m c_0(m)$ after substitution into
$$ \mathcal{T}_p(m)=2\mathcal{T}_p(m-1)+3^m m^2 $$
we obtain the recurrence
$$ c_0(m) = c_0(m-1) + m^2\left(\frac 32\right)^m $$
with solution
$$ c_0(m) = \left(\frac 32\right)^m\left(3m^2-12m+30\right)-30 $$
then
$$ \mathcal{T}(m) = \left(c_0+\left(\frac 32\right)^m\left(3m^2-12m+30\right)-30\right)2^m $$
going now backwards with $m = \log_3 n$ we obtain
$$ T(n) = 30n+3n(\log_3 n)^2-12n\log_3 n -30\cdot 2^{\log_3 n} $$
hence
$$ T(n) = \mathcal{O}\left(n(\log_3 n)^2\right) $$