A nested loop places one loop inside another. When each item must be compared with every other item, the repeated work can grow proportionally to the square of the input size, or O(n²). section 4.1.2
Checking for duplicate items
The outer loop selects an item, while the inner loop compares it with every item in the sequence. The function returns early when it finds a duplicate; otherwise, its worst case examines the full list. section 4.1.2
def has_duplicates(sequence):
for index1, item1 in enumerate(sequence): #1
for index2, item2 in enumerate(sequence): #2
if item1 == item2 and index1 != index2: #3
return True
return False
Inspect the Python implementation to see how the outer and inner loops compare items and avoid matching an item with itself. section 4.1.2
