Introduction

Generating all pairs from an array is a classic quadratic operation. The exact count depends on what you mean by "pair": unordered pairs, ordered pairs, or pairs that may include the same element twice.

Unordered Pairs Without Repetition

The most common interpretation is all pairs (a[i], a[j]) where i < j.

1def unordered_pairs(items):
2    pairs = []
3    for i in range(len(items)):
4        for j in range(i + 1, len(items)):
5            pairs.append((items[i], items[j]))
6    return pairs
7
8
9print(unordered_pairs([1, 2, 3, 4]))

If the array has length n, the number of such pairs is:

n * (n - 1) / 2

That is Theta(n^2) growth, so both the number of generated pairs and the running time are quadratic.

Ordered Pairs

If (a, b) and (b, a) both count as different pairs, then each position can pair with every other position.

1def ordered_pairs(items):
2    pairs = []
3    for i in range(len(items)):
4        for j in range(len(items)):
5            if i != j:
6                pairs.append((items[i], items[j]))
7    return pairs
8
9
10print(ordered_pairs([1, 2, 3]))

Now the count is:

n * (n - 1)

That is still Theta(n^2).

Including Self-Pairs

If pairs such as (a[i], a[i]) are allowed, there are n^2 pairs.

1def all_pairs_with_self(items):
2    return [(a, b) for a in items for b in items]
3
4
5print(all_pairs_with_self([1, 2, 3]))

Again, the time complexity is Theta(n^2).

You Cannot Output Quadratically Many Pairs Faster Than Quadratic Time

This is the key idea that often gets missed. If the output itself has Theta(n^2) size, then any algorithm that explicitly lists all pairs must take at least quadratic time just to produce them.

So asking for an O(n log n) or O(n) algorithm to generate every pair is usually asking for the impossible.

You can only do better if:

• you do not actually materialize every pair
• you count pairs instead of generating them
• you generate only a filtered subset

Space Complexity Depends On Whether You Materialize The Output

If you print or stream pairs one at a time, the extra memory is only the loop variables and temporary storage.

1def print_pairs(items):
2    for i in range(len(items)):
3        for j in range(i + 1, len(items)):
4            print(items[i], items[j])

This still takes Theta(n^2) time, but only O(1) auxiliary space.

If instead you store every pair in a list, the output structure itself also requires Theta(n^2) space.

That distinction matters when n is large.

Counting Pairs Is Different From Generating Pairs

If you only need the number of unordered pairs, you do not need nested loops at all.

1def count_unordered_pairs(n):
2    return n * (n - 1) // 2
3
4
5print(count_unordered_pairs(4))

This is O(1) time because you are computing the count directly rather than emitting each pair.

That is often the real optimization people want.

Common Pitfalls

The most common mistake is confusing counting with generating. Counting can be constant time, but generating every pair cannot be.

Another mistake is forgetting to define whether order matters. n * (n - 1) / 2 and n * (n - 1) describe different outputs.

Developers also overlook space usage. Storing all pairs can become a much bigger problem than the loop itself.

Finally, writing the loops with list comprehensions or generators changes syntax, not asymptotic complexity.

Summary

• Unordered pairs without repetition take Theta(n^2) time to generate.
• Ordered pairs also take Theta(n^2) time.
• Including self-pairs still leaves the problem quadratic.
• If the output has quadratic size, explicit generation cannot be asymptotically faster.
• Counting pairs is easier than generating them and may be O(1).