Solve using substitution method solve $T(n) = T(n-1) + n$ by guessing $O(n)$

Question

I'm still learning the substitution method and I'm a bit confused on how to find out whether my guess in fact correct or not

Here's what I did so far:

Induction goal: $T(n) ≤ cn$
Induction hypothesis: $T(n-1) ≤ c(n-1)$

\begin{split} T(n)&=T(n−1)+n≤c(n−1)+n \\ &=cn−c+n≤cn \end{split} $$c \geq n$$

I don't know what I'm supposed to conclude from this, or from most substitutions I do.

Answer 1

You assume that $c$ must be constant but find a contradictory inequality, i.e., $c \geq n$. Hence, your assumption has been disputed. Thus, your guess is not correct.

To find the final value, you can easily do it by substitution like the following:

$$ T(n) = T(n-1) + n = T(n-2) + (n-1) + n $$

Now, by induction, we can show that the following if we assume that $T(1) = 1$:

$$ T(n) = \sum_{i=1}^n i $$

Therefore, $T(n) \in \Theta(n^2)$ and consequently $T(n) \in O(n^2)$.