How to show that $T(n) = T(n-1) + \Theta(n)$ is in $\Omega(n^2)$

Question

In the class we have been shown the way to prove that $T(n) = T(n-1) + \Theta(n)$ is in $O(n^2)$

$$ \begin{align} T(n)&\le T(n-1) +cn &\\ &\le c(n-1)^2+cn &\\ &=cn^2-2cn+c+cn\\ &=cn^2-cn+c\\ &=c(n^2-n+1)\le cn^2 &\ \end{align} $$

Then we were said that it is easy to see that $T(n) = T(n-1) + \Theta(n)$ is in $\Omega(n^2)$. But, I do not understand how to "see" this really. As I understand we need to show that

$$ T(n-1) + \Theta(n)\ge cn^2 $$ Right? I have no idea how to do that. Need help. Thank you!

Answer 1

Let $c$ be the lower bound so that your $\Theta (n)$ is greater than or equal to $cn$. Then you have

$$T(n) \geq T(1) + c\sum_{j=1}^n j = T(1) + cn(n+1)/2 = \Omega(n^2)$$

The only tricky thing there is knowing the formula for $\sum_{j=1}^n j$. But that's a classical result, you can look up sum of consecutive integers for example.

Answer 2

The following definition is useful for your purpose $f(n)=\Theta(g(n))$ means that

$$ c_1\, g(n) \leq f(n) \leq c_2 \,g(n) $$

for some positive $k_1,k_2$.