3

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)$.

Git Gud
  • 31,356
user2491173
  • 31
  • Let $\varphi\in \mathcal O(f)$. Now write the following definitions: $\varphi\in \mathcal O(f), f\in \mathcal O(g)$ and (your goal which is) $\varphi\in \mathcal O(g)$. Try to relate them. – Git Gud Mar 07 '15 at 15:23

0 Answers0