# 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

## closed as unclear what you're asking by D.W.♦, David Richerby, Luke Mathieson, Juho, Wandering LogicFeb 2 '15 at 12:59

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

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)$.