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