# Big O complexity of algorithm with a nested for loop only running once

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 []

• What does return [numbers.find(n), numbers.find(sum - n)] mean? Speak to me like I don't know Python. Because... I don't. Nov 8 '16 at 9:33
• You may profit from reading our reference questions.
– Raphael
Nov 8 '16 at 12:01
• @David Richerby It returns a list of two numbers. The first is the index of n in numbers. find(n) goes through numbers and return the index of the first element equal to n. Same afterwards for sum - n. Nov 8 '16 at 22:28

Both of you are correct. The algorithm runs in time $O(n^2)$ (where $n$ is the size of numbers), and it also runs in time $O(n)$.
Big O is only an upper bound on the running time. The algorithm also runs in $O(n^3)$, in $O(n\log n)$, in $O(2^n)$, and in $O(f(n))$ for many other (in fact, infinitely many) functions $f(n)$.