Sriram Sriram - 3 months ago 22
Python Question

Time complexity for lookup in dictionary.values() lists vs sets

In Python, we know that looking up a key in a dictionary takes O(1) run time, but what is the run time to look up in the dictionary.values() ?

dictionary = {'a':[66,77,88], 'b':[99,100]}
key = 'a'
if key in dictionary: # takes O(1) run time

number = '99'
if number in dictionary.values(): # What is the run time here?


Edit #1: The values for the keys could be either lists or sets. Many folks have responded that if the values are lists the run time is O(1).

Will it be O(N) if values are sets?

dictionary = {'a':(66,77,88), 'b':(99,100)}
number = '99'
if number in dictionary.values(): # What is the run time here?

BPL BPL
Answer

Let be x in s the operation which searches in a list, {x=item , s=list}

The average case - assuming parameters generated uniformly at random - for such operation will be O(n)

For more info about time complexity, here's the official link