# Solving Recurrence Relations 3 [closed]

Consider the following recurrence $$T(n)=T(n-1)+n\log n$$

My approach: Solving using Substitution $T(n)=n \log n+(n-1) \log (n-1)+(n-2) \log (n-2)+(n-3) \log (n-3)+...$

$=[n\log n + n \log(n-1)+ n \log(n-2)+ n \log(n-3)+...]-[\log(n-1)+2\log(n-2)+3\log(n-3)+...]$

$=[n(\log n + \log(n-1)+ \log(n-2)+ \log(n-3)+...)]-[\log(n-1)+2\log(n-2)+3\log(n-3)+...]$

$=[n(\log(n(n-1)(n-2)(n-3)+...)]-[\log(n-1)+2\log(n-2)+3\log(n-3)+...]$

$=[n(\log n!)]-[\log(n-1)+2\log(n-2)+3\log(n-3)+...]$

$\approx O(n^2 \log n)$

But ans is given as $O(n \log n)$. What have I done wrong

Your answer is correct. $O(n \log n)$ is wrong. This is easily shown by considering the sum of $j \log j$ over $j=n/2,\dots,n-1,n$; each term is at least $\frac12 n \log (n/2)$, and there are $n/2$ terms, so the total sum is at least $\frac14 n^2 \log(n/2)$, which is $\Theta(n^2 \log n)$.