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?