0

I want to prove the following $$\Omega(f(n)) \subset \Omega(g(n)), iff : g(n)\in \mathcal{O}(f(n)) \wedge f(n) \not\in \mathcal{O}(g(n))$$
What I did so far is:
$$t(n)\in\Omega(f(n)) \rightarrow \exists c_{1} \exists n_{0} \forall n>n_{0} , t(n)\geq c_{1}\cdot f(n)$$ Now I need to use the given details:
$$g(n)\in \mathcal{O}(f(n)) \rightarrow \exists c_{2} \exists n_{1} \forall n>n_{1} , g(n)\leq c_{2}\cdot f(n)$$


$$\frac{1}{c1}\cdot t(n) \geq f(n)$$ $$\frac{1}{c2}\cdot g(n) \leq f(n)$$ $$\rightarrow \frac{1}{c2}\cdot g(n) \leq f(n) \leq \frac{1}{c1}\cdot t(n) $$ $$\rightarrow t(n) \in \Omega(g(n))$$
I dont know how to continue and I dont know if its right
any suggestions?
thanks.

Ofir Attia
  • 3,136

1 Answers1

1

Let's start with $f(n) \in \Omega(f(n))$. Since $\Omega(f(n)) \subset \Omega(g(n))$, we have $g(n) \in O(f(n))$ by partial ordering. You showed this correctly and more formally above. If you have already proven partial ordering of Big-O and Big-Omega, it's easier to use that.

Now, since $\Omega(f(n)) \subset \Omega(g(n))$, we let $j(n) \in \Omega(g(n))$ with $j(n) \not \in \Omega(f(n))$ by definition of a proper subset. And so since $j(n) \not \geq C * f(n)$ (for all $n \geq n_{0}$), we have $j(n) < C * f(n)$, which implies $j(n) \in O(f(n))$. And so we have this strict inequality that $c_{1} g(n) \leq j(n) < c_{2} f(n)$. Thus, $g(n) \not \in O(f(n))$.

I leave the other side for you.

ml0105
  • 14,674
  • How you can say that $j(n) \not\in \Omega(f(n)) $ its something we need to prove.. its not given.. right? – Ofir Attia Apr 02 '14 at 14:06
  • We're given $\Omega(f(n)) \subset \Omega(g(n))$. So by definition of a proper subset (note $\subset$ vs. $\subseteq$), we have such an element $j(n)$. – ml0105 Apr 02 '14 at 14:07
  • I know.. but how I can use it? this is what I need to prove, its not given to me , the only thing its given and I need to use its what after "$iff$" – Ofir Attia Apr 02 '14 at 14:09
  • what I wrote above it enough for the first side? – Ofir Attia Apr 02 '14 at 14:10
  • Which is exactly what I've done above. I'm just applying definitions. What does it mean for $j(n) \not \in \Omega(f(n))$? It means we can't have $j(n) \geq C * f(n)$ (for any $C$). So $j(n) < C * f(n)$. Now what is the definition of Big-O? I'm just applying that. – ml0105 Apr 02 '14 at 14:11
  • No, it is not enough for the first side. You're showing something trivial, which has already been given. You have to conclude that since $t(n) \in \Omega(g(n))$ that $g(n) \in O(f(n))$. I showed you how to do this. – ml0105 Apr 02 '14 at 14:12
  • $j(n) < C\cdot f(n) $ implies that its not $\in \mathcal{O}(f(n)) $ by definition right? its need to be $\leq$ ..? – Ofir Attia Apr 02 '14 at 14:32
  • That is correct. – ml0105 Apr 02 '14 at 14:34
  • I dont understand you said we have $j(n) < C * f(n)$, which implies $j(n) \not \in O(f(n))$ how it can be? its implies that its $\in \mathcal{O}(f(n))$ – Ofir Attia Apr 02 '14 at 14:38
  • Sorry for the typo. I've fixed that. Really what we have is $c_{1} * g(n) \leq j(n) < c_{2} * f(n)$. So we have a strict inequality that $g(n) \leq k * f(n)$. Can $f(n)$ then be in $O(g(n))$? – ml0105 Apr 02 '14 at 14:43
  • $g(n) \in \mathcal{O}(f(n)) $ not say that $f(n) \not\in \mathcal{O}(g(n))$ – Ofir Attia Apr 02 '14 at 14:52
  • Since we have a strict inequality, can $f(n) \in O(g(n))$? That's the punchline. – ml0105 Apr 02 '14 at 14:53
  • OK Got it, the second side I start with $$t(n)\in \Omega(f(n))$$ and $$t(n)\in \Omega(g(n))$$? – Ofir Attia Apr 02 '14 at 15:04
  • You start with $g(n) \in \Omega(f(n))$ and $f(n) \not \in O(g(n))$. So you have $C * g(n) < f(n)$. – ml0105 Apr 02 '14 at 15:31
  • what about it: $$1.t(n)\in \Omega(f(n)), 2.t(n)\in \Omega(g(n))$$ so $$t(n)\geq c_{2}\cdot f(n), t(n) \geq c_{3}\cdot g(n)$$ now we have to cases to check one with $g(n)\geq f(n)$ and the opposite, now we can infer the two conditions. – Ofir Attia Apr 02 '14 at 15:42
  • You generally start with the assumptions. I think you're doing things the long way, and you're assuming a bit of what you're trying to prove. Start with the assumptions. What happens if $t(n) \in \Omega(f(n))$? What does this imply about $t(n)$ being in $\Omega(g(n))$? Now what happens if $C*g(n) < t(n) < f(n)$? – ml0105 Apr 02 '14 at 15:45