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
  • 929
  • 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

1 Answers1

5

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,532
  • 7
  • 47
  • 105