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

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!

• Do you know how they got the first inequality? – science Feb 12 '15 at 19:06
• @science not exactly... – UserMoon Feb 12 '15 at 19:08
• So how can you prove the other case? – science Feb 12 '15 at 19:15
• @science well, I guess we just assumed $T(n) <= O(n^2)$ and this we substituted T(n-1) with squared expression. That is what I understand – UserMoon Feb 12 '15 at 19:16

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.

• I did not really understand anything :( could you give more detailed explanation please – UserMoon Feb 12 '15 at 19:09
• @UserMoon: en.wikipedia.org/wiki/Triangular_number – Fizz Feb 12 '15 at 20:04

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$.

• We need to prove that recurrence is in Theta and thus we should show bigO and Omega – UserMoon Feb 12 '15 at 19:31
• The title says in $\Omega$! – science Feb 12 '15 at 19:36