finding big theta notation with recursion and nlg(n)

Question

given the recursion formula: $T(n) = T(n-1) + n\cdot \lg{n}$ I need to find $g(n)$ so that $T(n)=\theta(g(n))$. I know that $T(n) = n\cdot \lg n + (n-1)\cdot \lg (n-1) + (n-2)\cdot \lg (n-2 + ... = \sum_{i=2}^{n}i\cdot \lg{n} + \theta(1) \le n^2\cdot\lg{n} + \theta(1)\Longrightarrow T(n)=O(n^2\cdot\lg{n})$ but I can't find a way to prove $T(n)=\Omega(n^2\cdot\lg{n})$ and I don't see another function that can be $g(n)$ other than $n^2\cdot\lg{n}$

Answer 1

Assuming that $T(n) = \sum\limits_{i=2}^n i \lg i + \Theta(1)$, we have $$ T(n) > O(n)+ \sum\limits_{i=n/2}^n i \lg i > O(n) + \sum\limits_{i=n/2}^{n} \frac{n}{2} \lg \frac{n}{2} > O(n)+ \sum\limits_{i=n/2}^n \Omega( n \lg n) = O(n) + \Omega(n^2 \lg n). $$ Basically, the sum included at least roughly $n/2$ summands that exceed $n/2 \lg (n/2) > (n \lg n)/2 + O(n)$