1

So I am working on my assignment and have gotten stuck. For previous questions I was able to use Master Theorem to get $\Theta$, but can't use the theorem for this question..

I know to get $\Theta$ I need to prove $O$ and $\Omega$, but I am not sure how to approach it. By this I mean I have solved the recurrence and gotten an $O$, what needs to be done differently to get $\Omega$?

Maybe I'll try and explain with an example. Say we have the recurrence: $T(n) = T(n-1) + 1$. I would approach this question by expanding: $$ \begin{align*} T(n) &= T(n-1) + 1 \\ &= (T(n-2) + 1) + 1 \\ &= (T(n-3) + 1) + 2 \\ &\ldots \end{align*} $$ which implies $O(n)$.

How would I go about the above differently to get Θ?

Yuval Filmus
  • 57,157
user112747
  • 29
  • 1
  • 5

1 Answers1

2

Your example is a very bad one, since your expansion actually shows that $T(n) = n + T(0) = \Theta(n)$. In general, if you use $\leq$ in your expansion then you only get an $O(\cdot)$ bound, while if you use $\geq$ in your expansion then you only get an $\Omega(\cdot)$ bound. If you get a formula for $T(n)$ then it is usually easy to obtain $\Theta(\cdot)$ asymptotics.

Perhaps it's best if you tell us the actual example that's stumping you, what you tried, and where you got stuck.

Yuval Filmus
  • 57,157
  • Oh, I see. The question would be T(n)=T(n−1)+2, where I come to the pattern T(n) = T(n-k) + 2k, when k = n-1 we get to T(n) = T(1) + 2(n - 1). This gives us O(n), no? How would I find Ω(⋅)? – user112747 Sep 27 '14 at 20:39
  • If $T(n) = 2n + T(0)$ then $T(n) = \Theta(n)$. I don't see why you're limiting yourself to upper bounds only. Proving lower bounds and proving upper bounds is exactly the same, only when proving $T(n) = O(f(n))$ it is enough to show $T(n) \leq cf(n)$, while when proving $T(n) = \Omega(f(n))$ it is enough to show $T(n) \geq cf(n)$. If you know that $T(n) \approx cf(n)$ then you can conclude that $T(n) = \Theta(f(n))$ (assuming that the error is asymptotically smaller than $f(n)$, as is the case in your example). – Yuval Filmus Sep 27 '14 at 20:42
  • I see what you mean. This makes a lot more sense. Thank you! – user112747 Sep 27 '14 at 20:45