How to determine if the time complexity is O(m + n) or O(Math.max(m, n))

Question

I was going over this code but I'm struggling to understand how it is O(m + n) instead of O(Math.max(m, n)). Or is O(m + n) under O(Math.max(m, n)) anyways?

 int i = 0, j = 0, res = 0;
    while (i < houses.length) {
        while (j < heaters.length - 1
            && Math.abs(heaters[j + 1] - houses[i]) <= Math.abs(heaters[j] - houses[i])) {
            j++;
        }
        res = Math.max(res, Math.abs(heaters[j] - houses[i]));
        i++;
    }

There's an example on CTCI where the function returns an n sized array. It says that the space complexity of log(n) due to stack calls is dwarfed when calculating big O since n > logn, resulting in O(n) overall. O(n + logn) isn't mentioned in this example (4.4 for those curious).

Any explanation would be appreciated!

Answer 1

As you already guessed, under the Big-O-Notation it is both the same.

Both functions, m + n and max(m, n), are elements of the set O(m + n) = O(max(m, n).

---

Let's do the math:

m + n <= max(m, n) + max(m, n) = 2 * max(m, n) and also
max(m, n) <= m + n as long as min(m, n) >= 0 (however m, n >= 0 already)

So both functions are bounded by the other function (plus a constant factor), hence O(m + n) or O(max(m, n)), the sets are equal.

Here is the formal (1-dimensional) definition (from Wikipedia):

---

Intuitively it also makes sense as both functions just mean linear growth in both variables and nothing more.

---

[...] resulting in O(n) overall. O(n + logn) isn't mentioned [...]

I am unsure whether that is a question. Just note that both sets are again the same as n <= n + log(n) and also n + log(n) <= n + n = 2 * n, linear in n.