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!

  • $\begingroup$ Do you know how they got the first inequality? $\endgroup$ – science Feb 12 '15 at 19:06
  • $\begingroup$ @science not exactly... $\endgroup$ – UserMoon Feb 12 '15 at 19:08
  • $\begingroup$ So how can you prove the other case? $\endgroup$ – science Feb 12 '15 at 19:15
  • $\begingroup$ @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 $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ I did not really understand anything :( could you give more detailed explanation please $\endgroup$ – UserMoon Feb 12 '15 at 19:09
  • $\begingroup$ @UserMoon: en.wikipedia.org/wiki/Triangular_number $\endgroup$ – 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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.