[Solved] What’s the time complexity of T(n) = n⋅log(n) + T(n-1)? [closed]

by 


T(n) = n log n + (n-1) log (n-1) + ... + 1 log 1 + T(0)
     < n log n + (n-1) log n + ... 1 log n + T(0)
     = ( n + n-1 + n-2 + ... + 1) log n + T(0)
     = n(n+1)/2 ⋅ log n + T(0)

So it is in O(n² log n), if T(0) is also in O(n² log n).

Other way:

T(n) = n log n + (n-1) log (n-1) + ... + 1 log 1 + T(0)
     < n log n + n log (n-1) + ... + n log 1 + T(0)
     = n (log n + log (n-1) + ... + log 1) + T(0)
     = n log (n!) + T(0)
     < n log (nⁿ) + T(0)
     = n ⋅ n ⋅ log n + T(0)
     = n² log n

Edit:
You can also see a lower bound by the same way:

T(n) = n log n + (n-1) log (n-1) + ... + 1 log 1 + T(0)
     > n log n/2 + (n-1) log n/2 + ... + n/2 log n/2 + (n/2-1) log 1 + ... 1 log 1 + T(0)
     = ( n(n+1)/2-n/4(n/2+1) ) log n/2 + T(0)
     = (3/8 n² + 1/4 n) log n/2 + T(0)
     = (3/8 n² + 1/4 n) log n - (3/8 n² + 1/4 n) log 2
     = 3/8 n² log n + 1/4 n log n - (3/8 n² + 1/4 n) log 2

So T(n) is in Ω(n² log n).

Together you get Θ(n² log n) (as long as T(0) is in O(n² log n))

solved What’s the time complexity of T(n) = n⋅log(n) + T(n-1)? [closed]