1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.