What's the time complexity of T(n)=nlogn+T(n-1)?

303 Views Asked by At

The title says it all. The best I can come up with is that this expands to

T(0) + 1log 1 + 2log 2 + ... + (n-1)log (n - 1) + nlog n

which is

T(0) + log(1) + log(2^2) + ... + log(n^n)

or

T(0) + log(2^2×3^3×...×n^n)

which I have no idea how to solve or if it's even possible to.

1

There are 1 best solutions below

0
On BEST ANSWER

$$\sum_{k=1}^n k \ln k \approx \int_1^n x \ln x dx = (n^2/2) \ln(n) -n^2/4 + O(1)$$

It should not be too hard to show (using the error estimate for the rectangle rule) that the error in this approximation is of lower order than $n^2 \ln(n)$.