Introduction

An algorithm is O(n^2) when the amount of work grows proportionally to the square of the input size. The usual reason is not simply "there are two loops," but that the total count of basic operations adds up to something like n * n or the arithmetic series 1 + 2 + ... + n.

Full Nested Loops

The easiest quadratic pattern is a loop inside another loop where both range over about n elements:

1def compare_all_pairs(arr):
2    count = 0
3    for i in range(len(arr)):
4        for j in range(len(arr)):
5            count += 1
6    return count

If the input size is n, the outer loop runs n times and the inner loop runs n times for each outer iteration. Total work is:

n * n = n^2

That is the direct reason the algorithm is quadratic.

Shrinking Inner Loops Can Still Be Quadratic

Many real algorithms do not run the inner loop a full n times on every iteration. They look more like this:

1def triangle_work(n):
2    total = 0
3    for i in range(n):
4        for j in range(i, n):
5            total += 1
6    return total

Now the inner loop runs:

• 'n times on the first outer iteration'
• 'n - 1 times on the second'
• 'n - 2 times on the third'
• continuing down to 1

The total is:

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

That sum equals n(n + 1) / 2, which is Theta(n^2). The factor of 1/2 does not matter for Big-O.

Why Big-O Ignores Constants

Suppose an exact operation count is:

3n^2 + 5n + 7

For large n, the n^2 term dominates the others, so the growth rate is still quadratic. Big-O keeps the dominant term and discards:

• constant factors
• lower-order terms

That is why all of these are O(n^2):

• 'n^2'
• 'n^2 / 2'
• '7n^2 + 10n'

The algorithms may have different real running times, but they belong to the same asymptotic class.

Pairwise Comparison Example

A common interview example is comparing every unordered pair:

1def count_equal_pairs(arr):
2    pairs = 0
3    for i in range(len(arr)):
4        for j in range(i + 1, len(arr)):
5            if arr[i] == arr[j]:
6                pairs += 1
7    return pairs

This inner loop does not run n times for every i, but the total number of comparisons is still:

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

which is again Theta(n^2).

A Better Way to Analyze an Algorithm

When you want to justify O(n^2), do not guess from the shape of the code. Count the unit of work.

Ask:

1. What is one basic operation?
2. How many times can it happen?
3. Does the total count simplify to n^2 or an equivalent quadratic sum?

This method works even when loops are irregular or the code is recursive.

When Two Loops Are Not Quadratic

Two loops do not automatically imply O(n^2). For example:

1def not_quadratic(n):
2    i = 1
3    while i < n:
4        i *= 2
5
6    for _ in range(n):
7        pass

This is O(log n + n), which simplifies to O(n), because the loops are sequential, not nested.

Even nested loops can be non-quadratic if the inner loop runs a constant number of times or shrinks geometrically.

Common Pitfalls

The biggest mistake is multiplying loop counts blindly without checking how the bounds actually depend on each other.

Another mistake is worrying about constant factors such as 1/2 and concluding the algorithm is not really quadratic. Big-O ignores constant multipliers.

People also forget the difference between worst-case and average-case analysis. Some algorithms are quadratic only in the worst case.

Finally, "nested loops means O(n^2)" is only a shortcut. Proper analysis comes from counting operations.

Summary

• An algorithm is O(n^2) when its dominant work grows proportionally to the square of the input size.
• Full nested loops are the clearest quadratic pattern.
• Shrinking inner loops can still be quadratic because 1 + 2 + ... + n is Theta(n^2).
• Big-O ignores constant factors and lower-order terms.
• The correct way to justify O(n^2) is to count operations, not guess from code shape.
  • Compare 3 and 2, swap → [1, 2, 3].
  • Compare 1 and 2, no swap needed.