1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ :-/ I probably should've used that instead... :D Oh well! +1 $\endgroup$ – Simply Beautiful Art Jan 24 '17 at 21:25
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.