Introduction

A nested loop does not automatically mean O(n²). The right question is not "Are there two loops?" but "How many total times can the inner body run as n grows?"

Count Total Work, Not Visual Indentation

Big O analysis depends on the total number of primitive operations, not on how the code looks on the page. Two nested loops are O(n²) only if the inner loop runs about n times for each of the n outer iterations.

This classic example is quadratic:

1def all_pairs(values):
2    n = len(values)
3    for i in range(n):
4        for j in range(n):
5            print(i, j)

The inner body runs n x n times, so the complexity is O(n²).

Some Nested Loops Still Add Up to O(n)

Now look at a two-pointer style loop:

1def scan_once(values):
2    n = len(values)
3    j = 0
4
5    for i in range(n):
6        while j < n and values[j] < values[i]:
7            j += 1

At first glance, this looks like nested looping. But j never resets to 0. Across the whole function, j can increase at most n times total.

That means:

• the for loop contributes n iterations
• the while loop contributes at most n increments overall

So the total work is O(n), not O(n²).

This is one of the most common reasons people overestimate time complexity.

Shrinking Inner Loops Often Produce O(n²)

Now consider:

1def upper_triangle(values):
2    n = len(values)
3    for i in range(n):
4        for j in range(i + 1, n):
5            print(i, j)

Here the inner loop gets shorter as i grows, but the total is still:

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

That sum is proportional to n², so the algorithm is still O(n²).

This is where summation helps. A shrinking inner loop is not automatically better than quadratic. You need to add the total number of iterations, not guess from the fact that the range gets smaller.

Different Growth Patterns Can Hide in Similar Code

Nested loops can lead to very different complexities:

• 'O(n²) when both loops run about n times'
• 'O(n log n) when the inner loop halves or doubles each step'
• 'O(n) when a secondary pointer only moves forward overall'

For example:

1def logarithmic_inner(values):
2    n = len(values)
3    for i in range(n):
4        j = 1
5        while j < n:
6            j *= 2

The while loop runs about log n times for each outer iteration, so the total is O(n log n).

The visual structure resembles the previous examples, but the growth rule is different.

A Reliable Analysis Checklist

When you are unsure, walk through the loop body and ask:

1. What variable controls the inner loop
2. Does it reset on every outer iteration
3. How many times can it advance in total
4. Can I write the total work as a sum

If the inner loop resets to a range of size about n each time, think O(n²). If it shares progress across outer iterations, the total may be much smaller. If it changes multiplicatively, look for a logarithm.

This checklist is more reliable than relying on intuition about indentation.

Common Pitfalls

• Assuming any nested loop must be quadratic.
• Ignoring whether the inner pointer resets on each outer iteration.
• Looking only at the worst single iteration of the inner loop instead of summing the whole execution.
• Forgetting that arithmetic series such as 1 + 2 + ... + n are still quadratic in Big O terms.
• Missing multiplicative updates such as j *= 2, which change the complexity from linear inner work to logarithmic inner work.

Summary

• Nested loops are not automatically O(n²).
• Count the total number of times the inner body executes across the whole algorithm.
• If an inner pointer only moves forward overall, the total work can still be O(n).
• If the inner loop resets and runs across most of the input repeatedly, the algorithm is usually O(n²).
• Summations and progress bounds are the clearest way to tell O(n), O(n log n), and O(n²) apart.