How do I solve the following recurrence using substitution method?
$$T(n) = T(n-1)+C$$
I've found reference to so many examples on line but most of the examples are of the form
$$T(n) = T\left(\frac{n}{4}\right) + n$$
So, I am really struggling to understand it and to solve $T(n) = T(n-1)+C$ using substitution method.
I appreciate if someone could help me out.
Just start substituting, we have \begin{align*} T(n) &= T(n-1) + C \end{align*} Now, we use this again, but for $n-1$ instead of $n$, that is \begin{align*} T(n-1) &= T(n-2) + C \end{align*} Combining both, we get \begin{align*} T(n) &= T(n-1) + C\\ &= T(n-2) + C + C\\ &= T(n-2) + 2C \end{align*} Now, apply the recursion for $n-2$, giving \begin{align*} T(n) &= T(n-2) + 2C\\ &= T(n-3) + 3C \end{align*} The pattern should now be clear. Having applied the recursion $k$ times, we have \begin{align*} T(n) &= T(n-{\color{red} k}) + {\color{red} k}C\\ \end{align*} That is, for $k=n$ $$ T(n) = T(0) + nC $$