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
8
$\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 '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
  • 1
    $\begingroup$ Meaning, the runtime is equal to $O(n)$ if n > m, and $O(m)$ otherwise. $\endgroup$ 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
  • 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 '16 at 10:30

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.