3
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Levi Morrison May 1 '13 at 19:05
  • $\begingroup$ @LeviMorrison What do you mean by the maximum of n and m? If you're wondering about the $=$ there, yes, these do hold. $\endgroup$ – phant0m May 1 '13 at 19:08
  • $\begingroup$ Meaning, the runtime is equal to $O(n)$ if n > m, and $O(m)$ otherwise. $\endgroup$ – Levi Morrison May 1 '13 at 19:12
  • $\begingroup$ @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. $\endgroup$ – phant0m May 1 '13 at 19:15
  • $\begingroup$ @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. $\endgroup$ – Leonid Volnitsky Nov 4 '16 at 9:06

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.