# Solving retreat formulas

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

• 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 – 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))$$