11

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?
Sriram
  • 999
  • 2
  • 12
  • 29
  • `O(n)` of course as you at worst case have to look at every value. If using python2 just calling `.values()` alone creates a list of all values. – Padraic Cunningham Sep 07 '16 at 23:54
  • O(n). It has read all the values and compare with each of them. BTW, it won't work that way if you have lists as values. – zvone Sep 07 '16 at 23:54
  • basically it's `O(n)`. But if you want to look up in such values that are lists it won't be O(n) any more. – Mazdak Sep 07 '16 at 23:54
  • Typically it is of O(n), as it it is just passing through a list – James Sep 07 '16 at 23:55
  • You also asked a question 2 days ago that gave you the complexity for all python operations http://stackoverflow.com/questions/39338520/time-complexity-for-a-sublist-in-python – Padraic Cunningham Sep 08 '16 at 00:16
  • This question was closed wrongly because dict.values() does not return a list but a dictionary view. I believe it's still O(n) because values views are not set-like, in contrast to keys views. https://docs.python.org/3/library/stdtypes.html#dictionary-view-objects – qwr Aug 10 '23 at 05:07

1 Answers1

6

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

BPL
  • 9,632
  • 9
  • 59
  • 117
  • dict.values does not return a list though, it returns a view. In this case, values views are not set-like. https://docs.python.org/3/library/stdtypes.html#dictionary-view-objects – qwr Aug 10 '23 at 05:03