O(n²) Explained: Nested Loops and Hidden Quadratic Code

Quadratic time is the complexity class you meet first and fight most often. It is the cost of comparing everything with everything: a loop inside a loop over the same data. On ten items it is invisible; on ten thousand it is fifty million comparisons. This article is about that jump, and about the quadratic that hides inside one innocent line.

The problem it solves

You need to know before running it whether code will survive real input sizes. "It was instant on my test list" says nothing, because a quadratic algorithm is fast on small inputs. What you want is a rule that predicts growth:

• If doubling the input doubles the work, the code is linear, O(n).
• If doubling the input quadruples the work, it is quadratic, O(n²).
• At 100,000 items the first is trivial and the second is billions of steps.

The intuition

A nested loop over the same list is a machine for visiting pairs. Draw the items along the top and down the side of a grid: every square is one pair (i, j), and there are n × n squares. Two common loop shapes visit them:

• The full square, for i in range(n): for j in range(n), visits all n² ordered pairs, including each item with itself.
• The triangle, for j in range(i + 1, n), visits each unordered pair once: n(n - 1) / 2 of them. That is the lesson's duplicate check and the handshake count at a party.

The triangle does half the work of the square, and both are O(n²), because Big-O drops constant factors. The half is real; it just does not change how the cost grows. Double n and either shape does four times as much.

Two loops side by side cost n + n = 2n, which is O(n). Nesting multiplies; sequencing adds.

Nesting is a hint, not a proof. What matters is how many times the innermost body runs in total. If an inner index only moves forward and never resets, as in two pointers or sliding window code, the total is O(n). The reverse trap is more common: quadratic code with one visible loop, because something inside it is itself a loop. x in some_list, index, remove and pop(0) each scan or shift up to the whole list.

Watch it run

The animation draws the lesson's grid for six items. Every square is one possible pair, and a nested loop is a machine for visiting them. Then it starts: the outer loop holds i = 0 while the inner loop walks j = 1, then j = 2, one comparison per square, and the counter climbs. When j reaches the end, the outer loop moves to i = 1 and the inner loop restarts at j = 2, so each row is one square shorter than the last and only the upper triangle fills in. The readout keeps the full square in view, 36 squares, while the comparisons stop at 15. The last frame scales it up: 15 comparisons for 6 items, 4,950 for 100. Seventeen times the input costs 330 times the work. That is O(n²).

The code

The lesson's duplicate check with a counter on the inner body, the three loop shapes, a hidden quadratic and its set-based fix, and a nested loop that is secretly linear. Counting steps instead of timing them gives numbers that do not depend on the machine:

def has_duplicate(nums):
    """The lesson's nested loop, with a counter on the inner body."""
    comparisons, n = 0, len(nums)
    for i in range(n):
        for j in range(i + 1, n):                # only pairs with j after i
            comparisons += 1
            if nums[i] == nums[j]:
                return True, comparisons
    return False, comparisons

for n in (6, 100, 1_000, 2_000):
    print(n, has_duplicate(list(range(n)))[1])
# 6 15
# 100 4950
# 1000 499500
# 2000 1999000
print(round(1_999_000 / 499_500, 3))             # 4.002  double n, four times the work

def loop_shapes(n):
    square = sum(1 for i in range(n) for j in range(n))          # every ordered pair
    triangle = sum(1 for i in range(n) for j in range(i + 1, n)) # every unordered pair
    side_by_side = sum(1 for i in range(n)) + sum(1 for j in range(n))
    return square, triangle, side_by_side

print(loop_shapes(1_000))                        # (1000000, 499500, 2000)

def common_slow(a, b):
    steps, out = 0, []
    for x in a:
        for y in b:                              # what `x in b` does on a list
            steps += 1
            if x == y:
                out.append(x)
                break
    return out, steps

def common_fast(a, b):
    seen = set(b)                                # one pass over b
    return [x for x in a if x in seen], len(b) + len(a)

for n in (1_000, 2_000):
    a, b = list(range(0, 2 * n, 2)), list(range(n))
    print(n, common_slow(a, b)[1], common_fast(a, b)[1])
# 1000 750000 2000
# 2000 3000000 4000

def longest_run(nums):
    """Nested loops, but j never goes back: every index is visited once."""
    best, i, steps = 0, 0, 0
    while i < len(nums):
        j = i
        while j < len(nums) and nums[j] == nums[i]:
            j += 1
            steps += 1
        best, i = max(best, j - i), j
    return best, steps

print(longest_run([3, 3, 1, 1, 1, 2]))           # (3, 6)

common_slow is what [x for x in a if x in b] really does when b is a list. Doubling the input quadrupled its steps, from 750,000 to 3,000,000, while the set version only doubled. Next, a check on 3,000 seeded random cases: the duplicate check against a set, the full pair count when no duplicate exists, both intersections against each other, the longest run against itertools.groupby, and the step count of the "nested" loop against n:

import random
from itertools import groupby

rng = random.Random(33)
ok = True
for _ in range(3_000):
    n = rng.randint(0, 60)
    nums = [rng.randint(0, rng.choice([5, 50, 5_000])) for _ in range(n)]
    dup, comps = has_duplicate(nums)
    ok &= dup == (len(set(nums)) < n)               # brute force: a set drops repeats
    if not dup:
        ok &= comps == n * (n - 1) // 2             # every pair, exactly once
    b = [rng.randint(0, 40) for _ in range(rng.randint(0, 40))]
    ok &= common_slow(nums, b)[0] == common_fast(nums, b)[0]
    run, steps = longest_run(nums)
    ok &= run == max((len(list(g)) for _, g in groupby(nums)), default=0)
    ok &= steps == n                                # linear, despite the nesting
    m = rng.randint(0, 40)
    ok &= loop_shapes(m) == (m * m, m * (m - 1) // 2, 2 * m)
print(ok)                                           # True

The complexity

• Pair check: O(n²) time, about n² / 2 comparisons in the worst case, O(1) extra space.
• Set-based duplicate check or intersection: O(n) average time, O(n) extra space. That trade, memory for time, is the usual way out of a quadratic.
• Sort first: O(n log n) time, after which duplicates sit next to each other and one linear scan finds them.
• Two loops over different inputs: O(n · m), which is only O(n²) when both grow together.
• The Big-O cheat sheet puts quadratic next to the other classes, and the Python cheat sheet lists which list operations are hidden O(n) scans.

Where it goes wrong

• Calling n² / 2 "faster than O(n²)". It is half the work and the same growth rate.
• Labelling every nested loop quadratic. Count the total inner iterations; a pointer that never moves back is linear.
• Missing the loop inside a method call. in, index, remove, count, pop(0) and insert(0, x) on a list are O(n) each, so inside a loop they make it O(n²).
• Testing only small inputs. A quadratic on 1,000 items feels instant; on 1,000,000 it is a trillion steps.
• Treating quadratic as always wrong. For a few hundred items a simple pair loop is fine, and when the output itself lists every pair, nothing can beat O(n²).

When it shows up in interviews

Constantly, as the brute force you are expected to state and then beat. Two sum, contains-duplicate, container with most water and many array problems all start as a pair loop, and the follow-up is "can you do better?", answered by a hash set, sorting, or two pointers. Interviewers also hand you code and ask for its complexity, which is where hidden quadratics and secretly linear nested loops are tested. The complexity classes overview shows where O(n²) sits among the others.

How to say it in an interview

"The brute force compares every pair: an outer loop over i and an inner loop over j after i, which is n times n minus one over two comparisons, so O(n²). Doubling the input quadruples the work, which is too slow at a hundred thousand items. I can trade memory for time: put the values in a hash set as I go and check membership in O(1) average, so the whole thing is O(n) time and O(n) space. If memory is tight, sorting first gives O(n log n) and duplicates end up adjacent. I'd also watch for hidden quadratics, like in on a list inside a loop."