<s>[INST] How to simplify the summation of a recurrence relation After solving the recurrence relation
$$T(n) = 3T(\frac{n}{3}) + n\log(n)$$
I get following equation
$$T(n)=3kT(\frac{n}{3k})+ n\log(n) + n\log(\frac{n}{3}) + n\log(\frac{n}{3^2})+\dots+n\log(\frac{n}{3^k})$$
I don't know how to simplify the summation and how to know the asymptotic function?
 [/INST] Let $n=3^k$. We have,
$T(n)=3^kT(\frac{n}{3^k})+ n\log(n) + n\log(\frac{n}{3}) + n\log(\frac{n}{3^2})+\dots+n\log(\frac{n}{3^k})$
$=3^k.T(1)+n\log\left(n.\frac{n}{3^1}.\frac{n}{3^2}\ldots.\frac{n}{3^k}\right)$
$=3^k.1+n\log\left(n.\frac{n^k}{3^{1+2+\ldots+k}}\right)$ (since $T(1)=1$)
$=3^k+n\log\left(\frac{n^{k+1}}{3^{1+2+\ldots+k}}\right)$
$=3^k+n\log\left(\frac{(3^k)^{k+1}}{3^{k(k+1)/2}}\right)$
$=3^k+n\log\left(\frac{3^{k(k+1)}}{3^{k(k+1)/2}}\right)$
$=3^k+3^k\log\left(3^{k(k+1)/2}\right)$
$=3^k+3^k.k(k+1)/2.\log3$
$=3^k+\Theta(3^k.k^2)$
$=\Theta(3^k.k^2)$
$=\Theta(n.(\log n)^2)$ (since $n=3^k$)
Or use Master theorem:
$T(n) = 3T(\frac{n}{3}) + n\log(n)$, here $c_{crit}=\log_b a = \log_3 3 = 1$, $k=1$, hence, we have,
$T(n) = \Theta(n^{c_{crit}}\log^{k+1}n)=\Theta(n\log^2 n)$
</s>