O(n²) and Nested Loops

The Idea

When a loop runs inside another loop over the same data, you do n units of work n times. That is O(n²). It feels perfectly fine on ten items and freezes solid on ten thousand.

Real-World Example

Picture a party where every guest greets every other guest. Ten guests produce 45 handshakes; a hundred guests produce 4,950. The room grew ten times, but the greeting count grew a hundred times.

The Code

def has_duplicate(nums):
    n = len(nums)
    # outer loop picks each item...
    for i in range(n):
        # ...inner loop compares it against the rest
        for j in range(i + 1, n):
            if nums[i] == nums[j]:
                return True
    return False
# roughly n*n/2 comparisons -> O(n^2)

count = 0
for i in range(4):
  for j in range(4):
      count += 1
# count is now ___