I have been debating with someone about the big O complexity of the following algorithm. We have a different understanding of the theory. Basically one of us thinks that this algo is automatically O(N^2) since there is a loop over N elements and another potential other loop over N elements inside the loop. The other one thinks that since the second loop over N will only ever be executed once, the complexity is O(N). Help!
Here is the algorithm in Python:
def get_indexes(numbers, sum):
s = set(numbers)
for n in numbers:
if n >= sum:
continue
if (sum - n) in s:
return [numbers.find(n), numbers.find(sum - n)]
return []
return [numbers.find(n), numbers.find(sum - n)]
mean? Speak to me like I don't know Python. Because... I don't. $\endgroup$ – David Richerby Nov 8 '16 at 9:33