Worst-case performance describes the maximum time or resources an algorithm may require for inputs of a given size. Big O notation expresses this upper-bound behavior. section 4.1.1
Checking for duplicates
A duplicate checker can stop quickly when the first two items match. In the worst case—no duplicates, or duplicates appearing last—it compares all items through nested loops, producing O(n²) time. section 4.1.2
Use worst-case analysis to:
- Compare alternative algorithms for the same task. section 4.1.1
- See how increasing input size affects execution time. 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 nested-loop duplicate checker and identify the input arrangement that forces its worst case. section 4.1.2
