What is the meaning of $O(m+n)$?

Problem Detail: 

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).

Asked By : Frank

Answered By : A.Schulz

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\}).$$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3149