4
$\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$
2

1 Answer 1

9
$\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$
6
  • $\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$ May 1, 2013 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, 2013 at 19:08
  • 1
    $\begingroup$ Meaning, the runtime is equal to $O(n)$ if n > m, and $O(m)$ otherwise. $\endgroup$ May 1, 2013 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, 2013 at 19:15
  • 1
    $\begingroup$ @LeonidVolnitsky By "meaningful" I meant "has a meaning and can be (and is) used in mathematical communication, e.g. in a paper". $\endgroup$ Nov 4, 2016 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.