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!

@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

score 1 · Accepted Answer · answered Feb 12 '15 at 19:03

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.

answered Feb 12 '15 at 19:03

user2566092

26,142

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

science · Answer 2 · 2015-02-12T20:02:35.200

-1

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

edited Feb 12 '15 at 20:02

answered Feb 12 '15 at 19:30

science

2,900

We need to prove that recurrence is in Theta and thus we should show bigO and Omega – UserMoon Feb 12 '15 at 19:31
1

The title says in $\Omega$! – science Feb 12 '15 at 19:36

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

2 Answers2