2

I am stuck with this problem. $$O(f) = \bigcup_{g \in O(f)} O(g)$$ I have tried to prove it with the assumption that $g \in O(f) \rightarrow f \in O(f)$, which I already have proved, but I am not sure how to continue.

Has someone maybe an idea?

Thanks!

-- This is one of the assumptions I tried:

$$\text{Say } x \in O(g))$$ $$\rightarrow x \leq c_1 \cdot g(n)$$ $$\text{Because } g \in O(f) \text{ then:}$$ $$g \leq c_2 \cdot f(n)$$ $$\rightarrow x \leq c_1 \cdot g(n) \leq c_1 \cdot c_2 \cdot f(n)$$ $$\rightarrow x \in O(f)$$

Hans Hüttel
  • 4,271
MWP
  • 21
  • What do you mean by $UO(g)$? What does it mean to write $g \in O(f)$ above the $=$ sign? – Antonio Vargas Apr 27 '17 at 00:54
  • What I understood was a conjunction of all subsets of $O(g)$, as long as $g\in O(f)$. – MWP Apr 27 '17 at 20:18
  • The union operation is not written as a capital "U", nor does one use a superscript on the equality. The danger of inventing your own secret, private notation is that no-one will be able to read what you write. – Hans Hüttel Apr 27 '17 at 20:53

1 Answers1

1

This is more a set theory question: your problem is with the method to proof equality of sets.

The basic (and very important!) idea is to use the fact that $ A = B $ iff $ A \subseteq B $ and $ B \subseteq A $ (this is, in fact, the definition of eqality of sets).

So, first, let $ h \in \bigcup_{g \in G} {O(g)} $, than what do you know by the definition of the union?

In the advance, you'll find out that $ h \in O(f) $ and that's prove that $ \bigcup_{g \in O(f)} O(g) \subseteq O(f) $.

Afterwards, you'll have to prove the second direction.

And, finally, you'll be able to conclude that equality.

I am not Paul Erdos
  • 294