1
$\begingroup$

In the context of Upper bounds computaion and Big Oh Notation, I was wondering if the following could be proved... if they are equivalent.
$\mathcal{O}((log(n))^{-1}) = (\mathcal{O}(log(n)))^{-1}$

$\mathcal{O}((log(n))^{-1})$ can be rewritten as
$\mathcal{O}(1/(log(n)))$ which is
$\mathcal{O}(1)/ \mathcal{O}(log(n))$ . This can be simplified to
$1/ \mathcal{O}(log(n))$
which is the same as the RHS. Would this be a possible solution? Any mistakes that are pointed are welcome.

$\endgroup$
4
  • 1
    $\begingroup$ You are engaging in "arithmetics with Landau terms". While often done, there is something between no to a shaky mathematical foundation for that. First, you have to consider carefully what you want "1 / O(f)" to mean -- what is the multiplicative inverse of a set of functions? Depending on your answer, it may not be the same as "2 / O(f)", which would break your chain. Finally, note that "O(g/f) = O(g) / O(f)" almost certainly breaks for some meanings of "/" and many pairs of functions. $\endgroup$
    – Raphael
    Commented Jan 28, 2019 at 12:13
  • $\begingroup$ My recommendation is to stick with O(1/f). It's well-defined, unambiguous, and doesn't cause any issues. $\endgroup$
    – Raphael
    Commented Jan 28, 2019 at 12:14
  • $\begingroup$ As a final prompt for thought: $n \not\in O(1/\log n)$ but $1/n \in O(\log n)$. $\endgroup$
    – Raphael
    Commented Jan 28, 2019 at 12:15
  • $\begingroup$ @Raphael If I were to stick with O(1/f) , it cant be the same as 1/O(f) you mean.. $\endgroup$ Commented Jan 28, 2019 at 12:18

1 Answer 1

2
$\begingroup$

This kind of thing just doesn't work. For example, one of your intermediate terms is $O(1)/O(\log n)$. However any function $f$ can be written as $g/h$ where $g=O(1)$ and $h=O(\log n)$. If $f=O(1)$, then let $g=f$ and $h=1$. If $f=\Omega(1)$, then let $g=1$ and $h=1/f$.

For a more formal treatment, try to rewrite each of your statements that involve big-$O$ in terms of "There are constants $k$ and $n_0$ such that, for all $n\geq n_0$, $f(n)\leq k\,g(n)$." You'll probably find that it's not even clear what these formal statements should be and that, if you manage to figure that out, then some of the formal statements will be false.

The underlying point you've overlooked is that big-$O$ provides upper bounds but, if you have a quotient $a/b$ then upper-bounding that quotient requires upper-bounding $a$ and lower-bounding $b$. Big-$O$ can't express that lower bound.

$\endgroup$
3
  • $\begingroup$ It should be even better if the answer points out that $\mathcal{O}((\log(n)^{-1}) = (\mathcal{\Omega}(\log(n))^{-1}$ when only positive functions are considered. $\endgroup$
    – John L.
    Commented Jan 28, 2019 at 22:30
  • $\begingroup$ So do we have a counterexample? $\endgroup$ Commented Jan 29, 2019 at 13:03
  • $\begingroup$ @GermanShepherd A counterexample to what? $\endgroup$ Commented Jan 29, 2019 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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