How to solve $T(n) = T(n-1) + \log(n)$

Question

I need to demonstrate that the recurrence $T(n) = T(n-1)+\log(n)$ is $T(n) \le cn\log(n)$ using the substitution method.

I tried to substitute and I get $T(n) \le c(n-1)\log(n-1) + \log(n)$, but then I have no idea how to get rid of that $\log(n-1)$.

How can I demonstrate this?

Answer 1

$T(n)=T(0)+\sum_{k=1}^n\log(k)\leq T(0)+n\log(n)\leq cn\log(n).$

Answer 2

You could notice that solving directly yields

$$T(n)=T(0)+\log(n!)$$

and apply Stirling approximation:

$$T(n)\le T(0)+\log\left(\sqrt{2\pi n}\left(\frac ne\right)^n\right)=c+\frac12\log(n)+n\log(n)-n<n\log(n)$$

whenever $T(0)+\frac12\log(2\pi n)-n<0$.