Does one for loop mean a time complexity of n in this case?

Question

So, I've run into this problem in the daily coding problem challenge, and I've devised two solutions. However, I am unsure if one is better than the other in terms of time complexity (Big O).

# Given a list of numbers and a number k, 
# return whether any two numbers from the list add up to k.
#
# For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.
#
# Bonus: Can you do this in one pass?
# The above part seemed to denote this can be done in O(n).


def can_get_value(lst=[11, 15, 3, 7], k=17):
    for x in lst:
        for y in lst:
            if x+y == k:
                return True
    return False


def optimized_can_get_value(lst=[10, 15, 3, 7], k=17):
    temp = lst
    for x in lst:
        if k-x in temp:
            return True
        else:
            return False


def main():
    print(can_get_value())
    print(optimized_can_get_value())


if __name__ == "__main__":
    main()

I think the second is better than the first since it has one for loop, but I'm not sure if it is O(n), since I'm still running through two lists. Another solution I had in mind that was apparently a O(n) solution was using the python equivalent of "Java HashSets". Would appreciate confirmation, and explanation of why/why not it is O(n).

Your second function would be O(n**2) if it looped (thanks Mark Meyer...), as `if ... in temp` is O(n). See https://stackoverflow.com/questions/56226088/is-the-time-complexity-of-this-code-on2/56226204#56226204 for an O(n) solution. — Thierry Lathuille, May 21 '19 at 17:09
Actually your second function is O(1) because the loop returns after 1 iteration…unfortunately that also means it returns the wrong result or the correct result for the wrong reason. — Mark, May 21 '19 at 17:12
@Mark Meyer Thanks for your input. Why would it be O(1)? I'm speaking with the assumption that I would test with a different value: ex. optimized_can_get_value(lst=[1, 10, 3, 8], k=17). — Soo Kyung Ahn, May 23 '19 at 08:57
Oh, I realized it now: It's the return statement being at the wrong indentation level. Thanks — Soo Kyung Ahn, May 23 '19 at 08:59

Green Cloak Guy · Accepted Answer · 2019-05-21T17:16:11.047

2

The first solution can_get_value() is textbook O(n^2). You know this.

The second solution is as well. This is because elm in list has O(n) complexity, and you're executing it n times. O(n) * O(n) = O(n^2).

The O(n) solution here is to convert from a list into a set (or, well, any type of hash table - dict would work too). The following code runs through the list exactly twice, which is O(n):

def can_get_value(lst, k):
    st = set(lst)      # make a hashtable (set) where each key is the same as its value
    for x in st:       # this executes n times --> O(n)
        if k-x in st:  # unlike for lists, `in` is O(1) for hashtables
            return True
    return False

This is thus O(n) * O(1) = O(n) in most cases.

edited May 21 '19 at 17:16

answered May 21 '19 at 17:11

Green Cloak Guy

23,793
4
33
53

2

Though this works, it seems a bit odd to use a dictionary when you don't care about the values at all instead of just using `set(lst)`. – Nathan May 21 '19 at 17:14
you know what, I actually just forgot sets are hashtables too. Edited, thanks – Green Cloak Guy May 21 '19 at 17:16

Nathan · Answer 2 · 2019-05-21T17:27:37.130

In order to analyze the asymptotic runtime of your code, you need to know the runtime of each of the functions which you call as well. We generally think of arithmetic expressions like addition as being constant time (O(1)), so your first function has two for loops over n elements and the loop body only takes constant time, coming out to O(n * n * 1) = O(n^2).

The second function has only one for loop, but checking membership for a list is an O(n) function in the length of the list, so you still have O(n * n) = O(n^2). The latter option may still be faster (Python probably has optimized code for checking list membership), but it won't be asymptotically faster (the runtime still increases quadratically in n).

EDIT - as @Mark_Meyer pointed out, your second function is actually O(1) because there's a bug in it; sorry, I skimmed it and didn't notice. This answer assumes a corrected version of the second function like

def optimized_can_get_value(lst, k=17):
    for x in lst:
        if k - x in lst:
            return True
    return False

(Note - don't have a default value for you function which is mutable. See this SO question for the troubles that can bring. I also removed the temporary list because there's no need for that; it was just pointing to the same list object anyway.)

EDIT 2: for fun, here are a couple of O(n) solutions to this (both use that checking containment for a set is O(1)).

A one-liner which still stops as soon as a solution is found:

def get_value_one_liner(lst, k):
    return any(k - x in set(lst) for x in lst)

EDIT 3: I think this is actually O(n^2) because we call set(lst) for each x. Using Python 3.8's assignment expressions could, I think, give us a one-liner that is still efficient. Does anybody have a good Python <3.8 one-liner?

And a version which tries not to do extra work by building up a set as it goes (not sure if this is actually faster in practice than creating the whole set at the start; it probably depends on the actual input data):

def get_value_early_stop(lst, k):
    values = set()
    for x in lst:
        if x in values:
            return True
        values.add(k - x)
    return False

The second function can be improved by converting the list to a set. — Daniel Roseman, May 21 '19 at 17:12
Yes, I'm aware. The main question, though, was how to analyze the complexity of OP's current code. How to solve the problem efficiently is another question — Nathan, May 21 '19 at 17:13

Does one for loop mean a time complexity of n in this case?

2 Answers2