# O(1) — Constant time
def get_first(lst):
return lst[0] # Always one operation
# O(n) — Linear time
def find_max(lst):
max_val = lst[0]
for x in lst: # n iterations
if x > max_val:
max_val = x
return max_val
# O(n²) — Quadratic time
def has_duplicates(lst):
for i in range(len(lst)): # n iterations
for j in range(i+1, len(lst)): # ~n/2 iterations
if lst[i] == lst[j]:
return True
return False
# O(log n) — Logarithmic time
def binary_search(lst, target):
low, high = 0, len(lst) - 1
while low <= high: # Halves each time
mid = (low + high) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1# O(2^n) — Exponential (terrible!)
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2) # Two recursive calls!
# O(n log n) — Linearithmic (good for sorting)
def merge_sort(lst):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left = merge_sort(lst[:mid])
right = merge_sort(lst[mid:])
return merge(left, right)# O(1) space — in-place
def reverse_in_place(lst):
left, right = 0, len(lst) - 1
while left < right:
lst[left], lst[right] = lst[right], lst[left]
left += 1
right -= 1
# O(n) space — creates new list
def reversed_copy(lst):
return lst[::-1] # New list of size n
# O(n²) space — nested structures
def all_pairs(lst):Implement three versions of finding if a list has duplicates: 1) `has_dup_quadratic` — nested loops O(n²). 2) `has_dup_sort` — sort then check adjacent O(n log n). 3) `has_dup_set` — use set O(n). Write a `benchmark(func, data, label)` function using `time.perf_counter()` that times one call. Test all three with a list of 5000 elements (last element duplicates first). Print results with their Big-O labels.