2
$\begingroup$

I am thinking about the worst-case space complexity of an algorithm.

Obviously, if $f \in O(nm)$ then $f \in O(n+nm)$. But is the converse true?

$O(m)+O(nm) = O(m+nm) = O(m(1+n)) = O(m)O(1+n) = O(m)O(n) = O(nm)$

If that were true then $O(n+nm) = O(m+nm)$

$\endgroup$
  • 1
    $\begingroup$ Yes all that you have written is true including $O(n+nm)=O(m+nm)$ as $f\in O(n)\implies f\in O(nm)$ $\endgroup$ – User Not Found Jul 13 '17 at 3:58
  • $\begingroup$ If you are allowed to assume that $n,m \geq 1$, then all of these classes are equivalent. The fact that $f$ measures the worst-case space complexity of an algorithm is completely spurious here, however. $\endgroup$ – Yuval Filmus Jul 13 '17 at 5:25
  • 2
    $\begingroup$ Two-parameter Landau symbols are notoriously ill-defined and basically broken. Unless $n$ and $m$ have some functional relationship, i.e. you can look at only one limit process, the semantics are not at all clear, per se. $\endgroup$ – Raphael Jul 13 '17 at 5:31
  • 2
    $\begingroup$ @Raphael Would you mind adding a reference? I found a link to some paper by Howell, but it does not seem to have been published in a major CS journal or conference proceedings... $\endgroup$ – Mr Tsjolder Jul 13 '17 at 7:57
  • $\begingroup$ @MrTsjolder Some thoughts and references are given here and here. $\endgroup$ – Raphael Jul 13 '17 at 8:57
1
$\begingroup$

As mentioned in the question, obviously $O(nm) \subseteq O(n + nm)$ as $n,m \rightarrow \infty $.

The reverse is also true when $n, m$ grow ever larger:

For all $n,m \geq 1 : m +nm \leq nm+nm = 2nm$ and so: $O(m+nm) \subseteq O(nm+nm) = O(2nm) = O(nm)$ as $n,m \rightarrow \infty$.

$O(2nm) = O(nm)$ as $n,m \rightarrow \infty$ is a property of big-O that follows directly from the definition.

With respect to the penultimate line in the question (the long sequence of equalities), there is some unusual notation. To make sense there, the product of two sets must be an element-wise product such as $O(n) \cdot O(m) =\{fg ∣ f∈O(n), g∈O(m)\}$. The ‘$+$’ sign before the first equal sign probably means the Minkowski sum A+B={a+b ∣ a∈A and b∈B} instead of A∪B, but in both cases the first equality would hold.

$\endgroup$
  • $\begingroup$ "O(nm) ⊆ O(n + nm) as n,m→∞" -- which definition makes this a meaningful statement? The common O has only one limiting process. $\endgroup$ – Raphael Jul 15 '17 at 7:31

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.