How to solve the recurrence A(n) = A(n-1) + n*log(n)?

Question

Given the recurrence:
A(n) = A(n-1) + n*log(n).
How do I find the time complexity of A(n)?

Answer 1

A(n) = A(n-1) + nlog(n)

Look, your recurence says: take the previous value and add nlogn to it.

So... assuming that A(1) = log(1) is the first element of the sequence: A(n) = SUM from i = 1 to n (ilog(i)).

Why?

A(1) = log(1).
A(2) = log(1) + 2log(2).
A(3) = A(2) + 3log(3) = 1log(1) + 2log(2) + 3log(3).
.
.
.
A(n) = 1log(1) + 2log(2) + 3log(3) + ... + nlog(n)

This way of solving recursion can be always used when F(n) - F(n-1) is a non recursive function. In our case it's nlogn so it worked.

Similar rule can be used when F(n)/F(n-1) is a non recursive function. Then we use PI instead of SIGMA.

If I were asked to give it an upper bound I would suggest to try the following:

  log(n)   + log(n)   + log(n)   + log(n)   + ...
+            log(n-1) + log(n-1) + log(n-1) + ...
+                       log(n-2) + log(n-2) + ...
.
.
.

so

Now you have a very clear upper bound, so the big-o is there for free (O(nlog(n!))). In case you're looking for a big-theta you need to struggle a bit longer.