Proof $\mathcal{O}(f(n)) = \mathcal{O}(g(n)) \iff f(n) \in O(g(n)) \land g(n) \in \mathcal{O}(f(n))$

91 Views Asked by At

There is an exercise that ask me to prove this logic formula about the complexity of algorithms:

$\mathcal{O}(f(n)) = \mathcal{O}(g(n)) \iff f(n) \in O(g(n)) \land g(n) \in \mathcal{O}(f(n))$

Proof:

$\mathcal{O}(f(n)) = \mathcal{O}(g(n)) \implies f(n) \in O(g(n)) \land g(n) \in \mathcal{O}(f(n))$

is trivial from $f(n) \in O(f(n)) \land g(n) \in \mathcal{O}(g(n))$.

Now I want to prove the $ f(n) \in O(g(n)) \land g(n) \in \mathcal{O}(f(n)) \implies \mathcal{O}(f(n)) = \mathcal{O}(g(n))$ so, in others words, I have to prove $\mathcal{O}(f(n)) \subseteq \mathcal{O}(g(n)) \land \mathcal{O}(g(n)) \subseteq \mathcal{O}(f(n))$.

Then, my question is, how can I use the definition of $f(n) \in O(g(n)) $ to conclude that $\mathcal{O}(f(n)) \subseteq \mathcal{O}(g(n))$?

$f(n) \in O(g(n)) $ means by definition that $\exists c \in \mathbb{R^+},n_0 \in \mathbb{N} $ such that $ \forall n \ge n_0, f(n) \le cg(n)$.