What is the time complexity of the following python code using dictionary?
Clash Royale CLAN TAG#URR8PPP
What is the time complexity of the following python code using dictionary?
def twoSum(self, nums, target):
compliments =
length = len(nums)
for i, num in enumerate(nums):
compliment_of_num = target-num
if compliment_of_num in compliments:
return [nums.index(compliment_of_num),i]
compliments.update(num:compliment_of_num)
I think its O(n) but I think the line " if compliment_of_num in compliments" is O(n) instead of O(1) which makes the complexity of the whole program to be O(N^2)
O(n)
in
dict
set
O(1)
So it means that it doesn't matter whether am looking in the set of keys or in the set of values. It's always O(1). Is it correct?
– Learner
Aug 10 at 5:05
dictionary is implemented as a hashtable and its search time is constant O(1)
– Albin Paul
Aug 10 at 5:06
No, the keys are O(1), not the values
– Reblochon Masque
Aug 10 at 5:06
@AChampion no it wouldn't, even if
dict.values() is O(1), and O(1) space, since it is a view, that doesn't mean membership testing is O(1). I'm pretty sure it's O(N), dicts are just fancy hash-maps after all. And I doubt that dict.values() creates an underlying hash-set of the values, or even more absurdly, an inverse-mapping, in any event, the dict_values view object doesn't support set operations for a reason...– juanpa.arrivillaga
Aug 10 at 5:34
dict.values()
dict.values()
dict_values
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
O(n)- theinfordict(likeset) isO(1)– AChampion
Aug 10 at 5:04