Using substitution method to prove asymptotic lower bound of $T(n) = T(n-1) + \Theta (n)$

Question

I try to prove that the asymptotics of the recurrence $ T(n) = T(n-1) + \Theta (n) $ is $ T(n) = \Theta(n^2) $.

By $\Theta$, I mean tight bound from above and below.

---

I can write the equation like this: $$ T(n) = T(n-1) + \Theta (n) = T(n-1) + cn. $$

I'm having a hard time proving the lower bound with this method, do you have any idea how?

What I did for Upper bound is:

Assume: $$ T(n-1) \leq c(n-1)^2, \quad c \in R $$

Therefore: $$ T(n) \leq c(n-1)^2 + cn = cn^2 - 2cn + c + cn = cn^2 - cn + c \leq cn^2 $$

Therefore I get: $$ T(n) \leq O(n^2) $$

For $O$, by which I mean just an upper bound.

So, how do I prove a matching lower bound using this method?

Answer 1

Let $f(n) = \Theta(n)$. Thus there are $N,a,b>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). $$