O(n²): Nested Loops
When work multiplies.
Put one loop inside another, and the work multiplies. For every item, you look at every other item. It's fine for a hundred items. For a hundred thousand, it can take hours.

- A loop inside a loop
- The work multiplies
- Fine small, terrible big
Finding duplicates, slowly
Here's a simple way to check for duplicates. Compare every number with every number after it. The inner loop runs for each step of the outer loop. We count the comparisons. Run it. Ten times more items gives about one hundred times more work. That's O of N squared.
def has_duplicate(nums):
checks = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
checks += 1
if nums[i] == nums[j]:
return True, checks
return False, checks
for n in [100, 1000]:
print(n, "items:", has_duplicate(list(range(n)))[1], "checks")100 items: 4950 checks 1000 items: 499500 checks
Finding duplicates, fast
Now a better way. A set remembers what we've seen, and checking a set is O of one. So one loop is enough. The whole thing is O of N. Run it. A million numbers, checked in a blink.
def has_duplicate(nums):
seen = set()
for n in nums:
if n in seen:
return True
seen.add(n)
return False
print(has_duplicate(list(range(1_000_000))))
print(has_duplicate([3, 1, 4, 1, 5]))False True
Summary
Nested loops are usually O of N squared. A set or a dictionary can often turn that into O of N. Next, the magic of halving.
Key takeaways- Loop in a loop: O(n²)
- A set can fix it
- O(n) instead