Complexity Analysis
def nested_with_break(arr):
n = len(arr)
for i in range(n):
for j in range(n):
if arr[j] == arr[i]:
breakWhat is the time and space complexity?
Work it out before scrolling down.
Time
O(n²)
Space
O(1)
How to derive it
Trap: the break might suggest this is faster than O(n²). But Big-O is worst case. If no duplicates exist, the inner loop always runs to completion: n × n = O(n²). The break helps in practice (best case O(n)) but doesn't change the worst-case analysis.