How do you make an estimation for the substitution method, when the recursion tree did not help so much?
I have a recurrence $$T(n) = 5\cdot T(n/3) + n (\log n)^2$$ And upon doing the recurrence tree, I got a rather difficult running time
$$ \sum_{j=1}^{\log(n)/\log(3)} \frac{5^{j-1} n\log_2^2[n/(3^{j-1})]}{(3^{j-1})^2} $$
How do you go about solving this recurrence?
There is another closely related recurrence that admits an exact solution. Suppose we have $T(0)=0$ and $T(1)=T(2)=1$ and for $n\ge 3$ $$T(n) = 5 T(\lfloor n/3 \rfloor) + n \lfloor \log_3 n \rfloor^2.$$
It seems reasonable to use integer values here as the running time of an algorithm is a function of discrete quantities.
Furthermore let the base three representation of $n$ be $$n = \sum_{k=0}^{\lfloor \log_3 n \rfloor} d_k 3^k.$$
Then we can unroll the recurrence to obtain the following exact formula for $n\ge 3$ $$T(n) = 5^{\lfloor \log_3 n \rfloor} + \sum_{j=0}^{\lfloor \log_3 n \rfloor -1} 5^j \times (\lfloor \log_3 n \rfloor - j)^2 \times \sum_{k=j}^{\lfloor \log_3 n \rfloor} d_k 3^{k-j}.$$
Now to get an upper bound consider a string of value two digits to obtain $$T(n) \le 5^{\lfloor \log_3 n \rfloor} + \sum_{j=0}^{\lfloor \log_3 n \rfloor -1} 5^j \times (\lfloor \log_3 n \rfloor - j)^2 \times \sum_{k=j}^{\lfloor \log_3 n \rfloor} 2 \times 3^{k-j}.$$
This simplifies to
$$\frac{1457}{32} 5^{\lfloor \log_3 n \rfloor} -\frac{9}{2} \lfloor \log_3 n \rfloor^2 3^{\lfloor \log_3 n \rfloor} -\frac{45}{2} \lfloor \log_3 n \rfloor 3^{\lfloor \log_3 n \rfloor} - 45\times 3^{\lfloor \log_3 n \rfloor} \\ + \frac{1}{4} \lfloor \log_3 n \rfloor^2 + \frac{5}{8} \lfloor \log_3 n \rfloor + \frac{15}{32}.$$
This bound is actually attained and cannot be improved upon, just like the lower bound, which occurs with a one digit followed by zeroes to give
$$T(n) \ge 5^{\lfloor \log_3 n \rfloor} + \sum_{j=0}^{\lfloor \log_3 n \rfloor -1} 5^j \times (\lfloor \log_3 n \rfloor - j)^2 \times 3^{\lfloor \log_3 n \rfloor-j}.$$
This simplifies to $$16\times 5^{\lfloor \log_3 n \rfloor} - \frac{3}{2} \lfloor \log_3 n \rfloor^2 3^{\lfloor \log_3 n \rfloor} - \frac{15}{2} \lfloor \log_3 n \rfloor 3^{\lfloor \log_3 n \rfloor} - 15 \times 3^{\lfloor \log_3 n \rfloor}.$$
Joining the dominant terms of the upper and the lower bound we obtain the asymptotics $$5^{\lfloor \log_3 n \rfloor} \in \Theta\left(3^{\log_3 5 \times \log_3 n}\right) = \Theta\left(n^{\log_3 5}\right).$$
This is in agreement with what the Master theorem would produce.