# Big O notation of max?

I'm coding a few set comparisons and noting their big O's using different algorithms and set implementations. I got to one particular function and I decided that it is $O(max(n,m))$ runtime. Is that the proper way to express this?

The expression $O(\max(n,m))$ is meaningful, and we even have $O(n) + O(m) = O(n+m) = O(\max(n,m))$.

• Just to clarify: $O(n) + O(m)$ is the maximum of n and m? I've only really used expressions like $O(1)$, $O(n log n)$. I haven't seen any 'operators' or anything before. – Levi Morrison May 1 '13 at 19:05
• @LeviMorrison What do you mean by the maximum of n and m? If you're wondering about the $=$ there, yes, these do hold. – phant0m May 1 '13 at 19:08
• Meaning, the runtime is equal to $O(n)$ if n > m, and $O(m)$ otherwise. – Levi Morrison May 1 '13 at 19:12
• @LeviMorrison Yes, the argument is quite simple: Suppose $n > m$ and your function is in $\mathcal{O}(n + m)$: Then your function is also in $\mathcal{O}(n + n)$, which is the same as $\mathcal{O}(n)$ Combine that with the argument for $m > n$ and you can see that it also being in $\mathcal{O}(\text{max}(n, m))$ makes sense. Note that adding $\mathcal{O}$s together is a slight abuse of notation. – phant0m May 1 '13 at 19:15
• @Yuval Filmus. What "expression is meaningful" means? And BTW, I have my own, open similar question in StackOverflow. You are welcome to claim 200 bounty points there. – Leonid Volnitsky Nov 4 '16 at 9:06