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!)]-[\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 Logic Feb 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.

  • 1
    $\begingroup$ Your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. If you just want general feedback, you are welcome to visit us in Computer Science Chat. $\endgroup$ – D.W. Feb 1 '15 at 18:31

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


Not the answer you're looking for? Browse other questions tagged or ask your own question.