Introduction

Two for loops do not automatically mean O(n^2). The complexity depends on whether the loops run one after another, whether one loop is inside the other, and whether the inner loop bound changes with the outer loop index. Good analysis starts by counting how many total iterations actually happen.

Sequential Loops Add, They Do Not Multiply

If two loops run one after the other, their costs add.

1def sequential(n):
2    total = 0
3
4    for i in range(n):
5        total += i
6
7    for j in range(n):
8        total += j
9
10    return total

The first loop runs n times and the second loop also runs n times. Total work is about 2n, which simplifies to O(n).

That is the first common mistake: seeing two loops and assuming quadratic time even when they are not nested.

Fully Nested Loops Usually Multiply

If the inner loop runs n times for each of n outer iterations, the total is n * n.

1def nested(n):
2    count = 0
3
4    for i in range(n):
5        for j in range(n):
6            count += 1
7
8    return count

The inner statement runs n^2 times, so this is O(n^2).

More generally:

• outer loop a(n) times
• inner loop b(n) times per outer iteration
• total a(n) * b(n)

Variable Inner Bounds Change the Math

Not every nested loop is quadratic. Consider:

1def triangular(n):
2    count = 0
3
4    for i in range(n):
5        for j in range(i):
6            count += 1
7
8    return count

Here the inner loop runs:

• '0 times when i = 0'
• '1 time when i = 1'
• '2 times when i = 2'
• and so on

So total work is:

0 + 1 + 2 + ... + (n - 1)

That arithmetic series sums to about n^2 / 2, which is still O(n^2) in Big O terms.

The coefficient changed, but the growth class did not.

Some Nested Loops Are Not Quadratic

The inner loop may shrink enough that the complexity changes.

1def logarithmic_inner(n):
2    count = 0
3
4    for i in range(n):
5        j = n
6        while j > 1:
7            j //= 2
8            count += 1
9
10    return count

The outer loop runs n times. The inner while loop runs about log n times. Total complexity is O(n log n).

So the real question is never "how many loops are there?" It is "how many times does the body execute as input grows?"

Ignore Constants, Keep Growth

Big O drops constants and lower-order terms. That is why:

• 'O(2n) becomes O(n)'
• 'O(n^2 / 2) becomes O(n^2)'
• 'O(n log n + n) becomes O(n log n)'

This does not mean constants are irrelevant in practice. It means they do not change the asymptotic growth class.

Count the Dominant Operation

When analyzing code, identify the operation that dominates runtime. For example:

1def mixed(n):
2    result = 0
3
4    for i in range(n):
5        result += i
6
7    for i in range(n):
8        for j in range(n):
9            result += i * j
10
11    return result

This function has one O(n) loop and one O(n^2) nested loop. The total is O(n + n^2), which simplifies to O(n^2) because the quadratic term dominates as n grows.

Common Pitfalls

• Assuming any two loops automatically mean O(n^2).
• Forgetting that sequential loops add rather than multiply.
• Ignoring changing inner bounds such as range(i) or while j > 1.
• Counting only loop syntax instead of counting actual body executions.
• Treating Big O as exact runtime instead of asymptotic growth.

Summary

• Two sequential loops are usually O(n), not O(n^2).
• Fully nested n by n loops are typically O(n^2).
• Changing inner bounds can still be quadratic or can become O(n log n) or something else.
• The correct method is to count how many times the inner work runs.
• Big O is about growth rate, not exact elapsed time.