I want to solve the following formula: $T(n)=T(n-1 )+ c\cdot\log n $, $T(1)=d$

I though about master but then I realized there is no dividing here so it's not gonna do it, I tried to expand the formula like this:

$T(n-1)=T(n-2) + c\cdot \log(n-1)$

$T(n-2)=T(n-3) + c\cdot \log(n-1)$

How do I find the general formula? How do I proceed from here? My professor taught us only master theory, no iteration

  • $\begingroup$ I encourage you to use latex (mathjax) instead of pictures, since it increase the quality of your question (and readability). For more information read here $\endgroup$ – Marcelo Fornet Jan 19 '18 at 16:58

If you unroll the formulae you get: $$T(n) = T(n-1) + c \cdot log(n) = \sum_{i=2}^{n} c\cdot log(i) + d = O(n \cdot log(n)) $$

Last equality is true from the following fact: $$\sum_{i=1}^n log(i) \ge \sum_{i=\frac{n}{2}}^n log(i) \ge \frac{n}{2} \cdot log(\frac{n}{2}) = O(n \cdot log(n))$$ $$\sum_{i=1}^n log(i) = log(n!) \le log(n^n) = n\cdot log(n) = O(n\cdot log(n))$$


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.