Вложенный цикл с ранним возвратом: лучший и худший случай
Дана функция:
def has_pair(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return True
return False
Как правильно описать сложность этой функции по времени?
- O(n^2) в любом случае: два вложенных цикла всегда дают квадрат
- O(1) в лучшем случае и O(n^2) в худшем
- O(n) в лучшем случае и O(n^2) в худшем: ранний `return` не может сработать раньше, чем внутренний цикл при i = 0 дойдёт до конца
- O(n log n) в среднем: внутренний цикл каждый раз короче предыдущего