what is the summation $\sum_{j=1}^{j=n}j \log j $?

Question

I come from Computer Science and I am not good in mathematics and numerical analysis. I proposed a recursive algorithm for a problem whose running time is $$T(n) = T(n-1) + O(n \log n).$$ Clearly its running time is

\begin{equation} \sum_{j=1}^{j=n}j \log j. \end{equation}

An obvious upper bound on its running time is $O(n^2\log n)$, I would like to know what exactly the summation \begin{equation} \sum_{j=1}^{j=n}j \log j \end{equation} is.

Thanks in advance

Answer 1

By partial integration,$$\int x\ln x=\frac12x^2\ln x-\int \frac12x^2\frac1x\,\mathrm dx =\frac12x^2\ln x-\frac14x^2+C$$ so that we get $$\sum_{j=1}^nj\ln j=\Theta(n^2\ln n),$$ i.e., you cannot reall yimprove upon your obvious upper bound.

Answer 2

There’s no closed form but it is asymptotic to $\int_{1}^{n}{x\log x} dx$ which is easy to evaluate