44
$\begingroup$

This is a basic question, but I'm thinking that $O(m+n)$ is the same as $O(\max(m,n))$, since the larger term should dominate as we go to infinity? Also, that would be different from $O(\min(m,n))$. Is that right? I keep seeing this notation, especially when discussing graph algorithms. For example, you routinely see: $O(|V| + |E|)$ (e.g. see here).

$\endgroup$

migrated from cstheory.stackexchange.com Aug 13 '12 at 19:00

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ maybe $m$ depends on $n$ $\endgroup$ – Andrew MacFie Aug 17 '12 at 13:32
33
$\begingroup$

You are right. Notice that the term $O(n+m)$ slightly abuses the classical big-O Notation, which is defined for functions in one variable. However there is a natural extension for multiple variables.

Simply speaking, since $$ \frac{1}{2}(m+n) \le \max\{m,n\} \le m+n \le 2 \max\{m,n\},$$ you can deduce that $O(n+m)$ and $O(\max\{m,n\})$ are equivalent asymptotic upper bounds.

On the other hand $O(n+m)$ is different from $O(\min\{n,m\})$, since if you set $n=2^m$, you get $$O(2^m+m)=O(2^m) \supsetneq O(m)=O(\min\{2^m,m\}).$$

$\endgroup$
  • 3
    $\begingroup$ I think it's noteworthy that they write in the abstract, "We show that it is impossible to define big-O notation for functions on more than one variable in a way that implies the properties commonly used in algorithm analysis. We also demonstrate that common definitions do not imply these properties even if the functions within the big-O notation are restricted to being strictly nondecreasing". $\endgroup$ – Raphael Sep 16 '14 at 8:24
  • 4
    $\begingroup$ As a follow-up to my above comment, the recent article A general definition of the O-notation for algorithm analysis by K. Rutanen (2015) does show how to define meaningful O-notation for general sets, including $\mathbb{N}^2$. $\endgroup$ – Raphael Sep 9 '15 at 11:52
25
$\begingroup$

Believe it or not, it seems (in my experience) that many algorithms people have actually not thought about what the big O notation formally means, and when asked about it, you can get several different answers. Some issues are discussed in the paper On Asymptotic Notation with Multiple Variables by Rodney R. Howell.

Curiously, it also seems that most introductory algorithms courses spend lots of time being very formal about big O notation with a single variable, and then the next weeks happily use the notation for graph algorithms with several variables in a casual way, without discussing what the notation actually means.

$\endgroup$
  • $\begingroup$ The link in my answer refers to the article of Howell, which is indeed a nice treatment on this question. $\endgroup$ – A.Schulz Aug 13 '12 at 19:52
  • 1
    $\begingroup$ @A.Schulz: Indeed, I was typing my answer simultaneously to you. $\endgroup$ – Kristoffer Arnsfelt Hansen Aug 13 '12 at 20:00
  • 1
    $\begingroup$ I am a proponent of being careful with Landau terms so I agree, but this contains too much rant for a good answer. $\endgroup$ – Raphael Aug 13 '12 at 22:22
  • 4
    $\begingroup$ @Raphael: The answer is not meant as a rant, but maybe it could have been phrased more precisely. The thing is, the question is basically, what is the meaning of big O with more than one parameter. The answer is, that it should mean whatever there is consensus about in the algorithms community, what is being taught in algorithms courses, etc. My point is, that there is seemingly not such a consensus about what the notation precisely means. $\endgroup$ – Kristoffer Arnsfelt Hansen Aug 14 '12 at 11:47

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.