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

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

| cite | improve this answer | |

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