Introduction

O(N + M) time complexity appears when an algorithm processes two independent inputs and touches each of them linearly. It is an important distinction because it describes work that scales with both sizes separately, instead of multiplying them together as O(N * M) would.

What O(N + M) Actually Means

When you see O(N + M), read it as "one pass over data of size N, plus one pass over data of size M." The algorithm is still linear, but linear in two dimensions.

This is common when:

• You merge or compare two collections.
• You traverse a graph represented as vertices plus edges.
• You preprocess one structure and then scan another.

The key idea is independence. If the amount of work done for one input does not repeat for every item in the other input, the complexity is usually additive rather than multiplicative.

Example: Merge Two Sorted Arrays

Merging two sorted arrays is a classic O(N + M) algorithm. You keep one pointer in each list, compare the current values, and append the smaller one to the result. Each element is consumed once.

1def merge_sorted(left, right):
2    i = 0
3    j = 0
4    merged = []
5
6    while i < len(left) and j < len(right):
7        if left[i] <= right[j]:
8            merged.append(left[i])
9            i += 1
10        else:
11            merged.append(right[j])
12            j += 1
13
14    merged.extend(left[i:])
15    merged.extend(right[j:])
16    return merged
17
18
19print(merge_sorted([1, 4, 8], [2, 3, 9, 10]))

Why is this O(N + M)?

• Each element in left is examined at most once.
• Each element in right is examined at most once.
• The cleanup step appends only the remaining unseen items.

There is no nested full scan, so the lists are not multiplying each other's cost.

Example: Graph Traversal

Depth-first search and breadth-first search on an adjacency-list graph are often described as O(V + E), which is the same pattern. V is the number of vertices and E is the number of edges.

1from collections import deque
2
3
4def bfs(graph, start):
5    visited = {start}
6    order = []
7    queue = deque([start])
8
9    while queue:
10        node = queue.popleft()
11        order.append(node)
12
13        for neighbor in graph[node]:
14            if neighbor not in visited:
15                visited.add(neighbor)
16                queue.append(neighbor)
17
18    return order
19
20
21graph = {
22    "A": ["B", "C"],
23    "B": ["D"],
24    "C": ["D"],
25    "D": []
26}
27
28print(bfs(graph, "A"))

The traversal visits every vertex once and inspects every edge once. That is why the complexity is additive. Even though there is a loop inside another loop, the total work across the whole run still sums to V + E, not V * E.

How To Tell Additive And Multiplicative Costs Apart

A good mental model is to ask one question: does the algorithm restart a full pass of one input for every element of the other input?

If yes, the cost tends to be multiplicative.

1def has_common_item_quadratic(a, b):
2    for x in a:
3        for y in b:
4            if x == y:
5                return True
6    return False

That function is O(N * M) in the worst case because every element of a may be compared with every element of b.

By contrast, a hash-based version is additive:

1def has_common_item_linear(a, b):
2    seen = set(a)   # O(N)
3    for item in b:  # O(M)
4        if item in seen:
5            return True
6    return False

This version is O(N + M) because building the set is one linear pass, then scanning the second list is another linear pass.

When O(N + M) Can Be Simplified

In asymptotic analysis, if N and M always grow together at roughly the same rate, some authors simplify O(N + M) to O(N). That is mathematically fine in a narrow context, but it hides useful information when the inputs represent different resources.

For example, if one array has ten items and the other has ten million, O(N + M) communicates the dominant cost much more honestly than a single O(N) symbol. In practice, keeping both variables visible usually makes the analysis clearer.

Common Pitfalls

The most common mistake is assuming that any nested loop must be O(N * M). That is not always true. Graph traversal is the standard counterexample because the inner iterations are spread across the edges collectively, not repeated from scratch for every vertex.

Another mistake is dropping one variable too early. If the algorithm truly depends on two independent sizes, writing only O(N) loses detail that matters for performance discussions and API design.

People also confuse O(N + M) with "slower than linear." It is still linear with respect to total input size. The plus sign does not make it a different class from practical linear-time behavior.

Finally, be careful with preprocessing. An algorithm may start as O(N + M) in theory, then become O(N log N + M) if you sort one input first. State each stage explicitly.

Summary

• 'O(N + M) means linear work over two independent inputs.'
• Merging sorted lists and traversing graphs are standard examples.
• Additive cost appears when each input is processed once, not repeatedly against the other.
• Nested loops do not automatically imply O(N * M).
• Keeping both variables visible often explains performance better than collapsing everything into one symbol.