Solve a recurrence with Big O

I have this recurrence:

T(n) = T(n-1) + O(n log n)

Then I guess the solution is T(n)=O(n log n) I use the substitution method.

T(n)<= c*(n-1)*log (n-1) + O(n log n)

T(n) <= c*n*log(n) + O(n 开发者_如何学Golog n) = O(n log n)

Is this correct?

I think this is incorrect. I think that the mistake is in the last step.

I think the correct answer is: T(n) = O(n^2 log n).

Here's why:

T(n) = T(n-1)+O(n log n)

T(n) = T(n-2) + O((n-1) log (n-1)) + O(n log n)

T(n) = T(n-3) + O((n-2) log (n-2)) + O((n-1) log (n-1)) + O(n log n)

.

.

.

T(n) >= O(n log n) + O((n-1) log (n-1)) + O((n-2) log (n-2)) + ... + O((n/2) log (n/2))

T(n) >= (n/2) * O((n/2) log (n/2))

T(n) >= O(n^2 log n)

On the other hand:

T(n) = T(n-3) + O((n-2) log (n-2)) + O((n-1) log (n-1)) + O(n log n)

.

.

.

T(n) <= n * O(n log n)

T(n) <= O(n^2 log n)

Hence:

T(n) = O(n^2 log n)