Using substitution method to prove asymptotic lower bound of $T(n) = T(n-1) + \Theta (n)$
Let $f(n) = \Theta(n)$. Thus there are $N,a,b&gt;0$ such that for $n \geq N$, we have $an \leq f(n) \leq bn$.

Now suppose that $T(n) = T(n-1) + f(n)$, with some base case $T(0) = C$. Unrolling the sum,
$$
T(n) = C + f(1) + \cdots + f(n).
$$
Let $D = C + f(1) + \cdots + f(N-1)$. For $n \geq N$,
$$
T(n) \leq D + b(N + \cdots + n) = D + b\frac{(n-N+1)(n+N)}{2} = O(n^2).
$$
Similarly,
$$
T(n) \geq D + a(N + \cdots + n) = D + a\frac{(n-N+1)(n+N)}{2} = \Omega(n^2).
$$