Introduction

The expression O(n) + O(n) = O(n) looks suspicious the first time you see it, because ordinary arithmetic says n + n = 2n. In asymptotic analysis, though, Big O notation does not track exact constants. It tracks how fast the running time grows as the input becomes large.

What Big O Is Actually Describing

Big O gives an upper bound on growth rate. When two algorithms both scale linearly with the input size, they both belong to the same class even if one takes twice as much work per element.

That is why these two loops have the same asymptotic complexity:

1def sum_values(values):
2    total = 0
3    for value in values:
4        total += value
5    return total
6
7
8def count_positive(values):
9    count = 0
10    for value in values:
11        if value > 0:
12            count += 1
13    return count

Each loop visits every element once, so each is O(n). If you run them one after the other, the total work is still linear.

Why O(n) + O(n) Collapses to O(n)

Suppose an algorithm performs two consecutive passes over the same input:

1def analyze(values):
2    total = 0
3    for value in values:
4        total += value
5
6    max_value = values[0]
7    for value in values:
8        if value > max_value:
9            max_value = value
10
11    return total, max_value

The first loop is O(n). The second loop is also O(n). So the exact running-time shape is closer to c1 * n + c2 * n, or (c1 + c2) * n. That is still linear growth, so the Big O class is O(n).

This is the same reason we simplify:

• 'O(3n) to O(n)'
• 'O(1000n) to O(n)'
• 'O(n + 5) to O(n)'

The constants matter in real performance, but they do not change the asymptotic category.

Exact Cost vs Asymptotic Cost

It is important not to confuse "same Big O" with "same speed." Two O(n) algorithms can behave very differently in practice.

For example:

1def one_pass(values):
2    result = 0
3    for value in values:
4        result += value
5    return result
6
7
8def ten_passes(values):
9    result = 0
10    for _ in range(10):
11        for value in values:
12            result += value
13    return result

Both are O(n), but ten_passes does about ten times as much work. Big O intentionally hides that constant factor because it is meant to compare long-run growth, not exact instruction counts.

If you care about concrete runtime, you still need benchmarking or more precise cost analysis.

When Addition Does Change the Result

The simplification only works when one term does not outgrow the other. If the costs have different growth rates, the dominant term wins.

Examples:

• 'O(n) + O(n^2) = O(n^2)'
• 'O(log n) + O(n) = O(n)'
• 'O(n) + O(n log n) = O(n log n)'

A simple example:

1def quadratic_then_linear(values):
2    for left in values:
3        for right in values:
4            _ = left + right
5
6    for value in values:
7        print(value)

The nested loop is O(n^2), and the final pass is O(n). The total is O(n^2 + n), which simplifies to O(n^2) because the quadratic term dominates for large n.

Sequential vs Nested Work

Another source of confusion is mixing sequential loops with nested loops. Two loops one after the other usually add:

1for x in items:
2    ...
3
4for y in items:
5    ...

That is O(n) + O(n), which becomes O(n).

A loop inside another loop multiplies:

for x in items:
    for y in items:
        ...

That is O(n * n), which is O(n^2).

This distinction matters more than the algebra itself. Many mistakes in complexity analysis happen because sequential work is accidentally treated like nested work, or the other way around.

A More Formal View

If f(n) and g(n) are both bounded above by a constant multiple of n, then their sum is also bounded above by a constant multiple of n.

In other words, if:

• 'f(n) <= c1 * n'
• 'g(n) <= c2 * n'

then:

• 'f(n) + g(n) <= (c1 + c2) * n'

That is exactly the definition needed to say the sum is still O(n).

Common Pitfalls

The main mistake is treating Big O like exact arithmetic instead of a growth-rate classification. Another is concluding that two O(n) algorithms are equally fast in practice, even though constant factors can matter a lot. Developers also often confuse consecutive loops with nested loops and accidentally turn addition into multiplication. A final problem is simplifying too early and losing the information that one linear algorithm makes two passes while another makes only one, which can still matter for real-world performance.

Summary

• 'O(n) + O(n) simplifies to O(n) because Big O ignores constant factors.'
• Two linear passes still grow linearly with input size.
• Same Big O does not mean same actual runtime.
• Different growth rates do not collapse the same way; the dominant term wins.
• Analyze whether work is sequential or nested before simplifying the expression.