# Time complexity O(m+n) Vs O(n)

Consider this algorithm iterating over 2 arrays (A and B)

size of A = n

size of B = m

Please note that m <= n

The algorithm is as follows

for every value in A:
// code

for every value in B:
// code


The time complexity of this algorithm is O(n+m) But given that m is strictly lesser than or equal to n, can this be considered as O(n)?

• Comments are not for extended discussion; this conversation has been moved to chat. – D.W. Apr 25 at 20:07

Yes:

$$n+m \le n+n=2n$$ which is $$O(n)$$, and thus $$O(n+m)=O(n)$$

For clarity, this is true only under the assumption that $$m\le n$$. Without this assumption, $$O(n)$$ and $$O(n+m)$$ are two different things - so it would be important to write $$O(n+m)$$ instead of $$O(n)$$.

• Comments are not for extended discussion; this conversation has been moved to chat. – D.W. Apr 25 at 20:09

Yes, since $$n + m \leq 2n$$ the algorithm is $$O(n)$$. However, you may wish to write $$O(m + n)$$ because it clearly shows which variables the algorithm depends on, and what each variable does to the complexity.

(expanding on my comment)

### Technically No

You need to be very careful here, as there is a difference between algorithmic time complexity and runtime. In the case you have described, the runtime may be O(n) but the algorithm itself is O(n+m).

This is because, without your external constraints, the algorithm's time complexity cannot be determined without knowing both m and n.

If you wanted to make the algorithm itself O(n), you would need to explicitly encode your external constraint that m<n within the algorithm itself. Adding a check that aborts if m>n would work.

### Unless...

The above does not hold if m < n by definition (ie it arises from a fundamental property of your data structures).

Say, for example, A is an array and B is an array composed of only the elements at the even indices of A. Then m is indeed < n by definition, and no check is required.

In cases like these the answer is yes, the algorithm is O(n). In fact, it would be 'incorrect' (assuming you are going for a tight upper bound) to say it is O(n+m) since the asymptotic performance depends entirely on n.

• Comments are not for extended discussion; this conversation has been moved to chat. – D.W. Apr 25 at 20:10