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
