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 &gt;= sum:
            continue
        if (sum - n) in s:
            return [numbers.find(n), numbers.find(sum - n)]
    return []
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)$.