# Proof involving asymptotic complexity

The question in Proof of big-o propositions asked to prove:

$$O(f(n))=O(g(n))\iff\Omega(f(n))=\Omega(g(n))\iff\Theta(f(n))=\Theta(g(n))$$

The accepted answer starts the proof with:

Suppose that $$O(f(n))=O(g(n))$$. It is easy to check that $$g(n)=O(g(n))$$ ... and so $$O(f(n))=O(g(n))$$ implies that $$g(n)=O(f(n))$$.

I believe that there is a mistake in quoted part of the answer above.

It claims that $$O(f(n))=O(g(n))\tag{1}$$

and $$g(n)=O(g(n))\tag{2}$$

implies

$$g(n)=O(f(n))\tag{3}$$

Using the interpretation given in "Introduction to Algorithms (CLRS) Edition 3, page 50", (1) is interpreted as $$\forall\Phi(n)\in O(f(n)), \exists\Psi(n)\in O(g(n))$$ such that $$\Phi(n)=\Psi(n)$$.

Additionally, the definition of $$O$$-notation given in "Introduction to Algorithms (CLRS) Edition 3, page 47" states:

$$O(g(n))=\{f(n):$$ there exist positive constants $$c$$ and $$n_0$$ such that $$0 \leq f(n)\leq c\cdot g(n)$$ for all $$n\geq n_0\}$$

Considering the counter example whereby $$f(n)=n$$ and $$g(n)=n^2$$. Then $$O(n)=O(n^2)$$ and $$n^2=O(n^2)$$ hold, but $$n^2\neq O(n)$$, thereby contradicting the assertion given in the accepted answer. Note: "$$\neq$$" in this case refers to "$$\not \in$$".

Therefore, I would like to ask if the answer provided is wrong or my interpretation and/or reasoning is wrong.

The notations $$a(n) = O(b(n))$$ and $$O(a(n)) = O(b(n))$$ have different meanings:

• $$a(n) = O(b(n))$$ means that $$a(n)$$ belongs to the collection of functions $$O(b(n))$$. That is, $$a(n) \in O(b(n))$$.
• $$O(a(n)) = O(b(n))$$ means (in this particular case) that the two collections of functions $$O(a(n))$$ and $$O(b(n))$$ are the same. That is, $$c(n) = O(a(n))$$ iff $$c(n) = O(b(n))$$.
(Usually $$O(a(n)) = O(b(n))$$ actually means $$O(a(n)) \subseteq O(b(n))$$.)

Big O notation is thus ambiguous, but in practice there is usually no confusion.