What is Time complexity of "set" and "if item in array" in Python?

Question

I need to check if a number and its double exist in an array. This code using set to solve it. However I am not sure the Time complexity is better than O(N^2). I use the for loop and if 2*item in s like below. Isn't it to know whether the item is in an array, we use another O(N). Which mean O(N^2) in total? If it is optimal, how can I implement the codes in C without using nested loop?
Thanks a lot!

  def checkIfExist(arr]) -> bool:
    s = set(array)
    for item in s:
        if 2 * item in s and item != 0:
            return True
    if arr.count(0) >= 2:
        return True
    return False

score 1 · Accepted Answer · answered Apr 24 '21 at 08:00

The time complexity of the 'in' operator for sets in python is on average O(1) and only in the worst case O(N), since sets in python use a HashTable internally.

So your function's time complexity on average should be O(N) and only in the worst case will be O(N^2), where N is the length of the array.

More here https://wiki.python.org/moin/TimeComplexity

What is Time complexity of "set" and "if item in array" in Python?

1 Answers1