O(N+M) time complexity

Question

I'm working through some practice problems where I'm given a target time complexity and space complexity. One of them gives a target time complexity of O(N+M). I'm having some trouble with the intuition of what an O(N+M) algorithm would look like. Does anyone have an example of an algorithm like this or can explain it clearly? Every example I try to think of seems like O(N*M) to me.

Answer 1

A simple example of algorithm that is O(m+n):

int sum(int[] nArr, int[] mArr) {
    int sum = 0;
    for(int i : nArr) {
        sum += i;
    }
    for(int i : mArr) {
        sum += i;
    }
    return sum;
}

To compute the sum, you need to go through all elements in nArr (size n) and all elements in mArr (size m), so the overall complexity is O(m+n)

Answer 2

Quick and simple example of an O(n + m) algorithm:

for (i = 0; i < n; i++)
{
  // do something but don't loop or invoke recursive functions
  // only constant O(c) complexity is allowed: a simple series of commands
}

for (i = 0; i < m; i++)
{
  // idem
}

Complexity is commutative when added (O(n + m) == O(m + n)) this means you may invert the two for() without affecting complexity. Obviously, on an algorithmic level the inverted one MAY not be equivalent to the straight one.

As an additional help, here is an example of O(n * m) algorithm:

for (i = 0; i < n; i++)
{
  for (j = 0; j < m; j++)
  {
    // do something but don't loop or invoke recursive functions
    // only constant O(c) complexity is allowed: a simple series of commands
  }
}

Again, you may invert inside with outside loop without affecting complexity (O(n * m) == O(m * n)). The same obvious considerations apply.

The limitation on what you may put into the for() bodies is because the big-o notation constraints the upper bound. If it were a lower bound (little-o notation) you may have put more complex stuff in, but it could never get less than that.

Answer 3

The intuition of this problem is that you have two unique variables n and m. Now imagine these two unique variables independently increasing, approaching infinity.

If this were an O(n) problem (i.e. BIG-O), the upward boundary of the complexity of this problem would be linear at least. You could say that O(n) = n^2. But an O(n) problem would never even get close to that n^2 limit as n (the input) approaches infinite.

Likewise, the behavior for m would be the same. O(m) can be m^2. But it is more accurate to say that O(m) = m. The complexities of these two problems are linear.

---

Now, if you just do O(n+m), is that really n^2? It shouldn't be. Even if n=m, the sum would be 2n or 2m. The complexity of this problem is still linear because the size of the output is still proportional to the inputs n and m. Therefore, the most precise answer to this problem would be O(n+m) = n+m.

Answer 4

So, in order to expand the other replies, I will try to add a example of such problems to help you understand:

• Find a min/max in a N sized array, and then look for this value in an M sized array. Since you need to perform first min/max search, you cannot do it at once.

For instance, summing up the elements of 2 vectors can be done in O(M+N), but it can be thought as O(N) (assuming N>M) or O(M) (if M>N).

Answer 5

All Above Answers illustrate how O(n+m) works but I would like to look at it from a different view by knowing what O(nm), what is the difference between O(n+m) and O(nm) the main difference is when multiplying an n number by m number it means that n will happen for m times or will try it for m times, for example, the below code is O(n*m) because n will happen m times for n times

for(int i=0; i < n;i++){
  for(int j=0; j < m;j++){
  //some_code
  }
}

Answer 6

One instructive example which does something non-trivial is to take two sorted arrays of size M and N and output a new sorted array with all of these elements. This is the basis of merge-sort and will take O(M+N) comparisons.

You can find an example anywhere or do it yourself.