2
$\begingroup$

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 []
| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ What does 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
  • $\begingroup$ You may profit from reading our reference questions. $\endgroup$ – Raphael♦ Nov 8 '16 at 12:01
  • $\begingroup$ @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. $\endgroup$ – Chuque Nov 8 '16 at 22:28
1
$\begingroup$

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)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ In what context does it go higher than O(N)? the initial for is N, then (sum - n) in s is O(1) since it's a set, but times N because of the loop. So we have 2*N. Then there are the two find functions that will be executed at most once each. So we have maximum 4*N, which amounts to O(N). Am I understanding the theory wrong? $\endgroup$ – Chuque Nov 8 '16 at 9:15
  • $\begingroup$ @Chuque Look up the definition of the big-O notation! You are thinking of Big-Theta notation. $\endgroup$ – DCTLib Nov 8 '16 at 9:18
  • $\begingroup$ O (x) basically means "not slower than x times a constant". Your algorithm is "not slower than n^12 times a constant", therefore by definition it is in O (n^12). $\endgroup$ – gnasher729 Nov 8 '16 at 10:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.