CODEWITHSUNDEEP
python
Aayush Scet
Aayush Scet

Reputation: 37

what is time complexity of python Dictionary.values()?

I have referred to this page but it shows Dict.keys()'s time complexity. https://wiki.python.org/moin/TimeComplexity

This sheet also shows the same https://www.geeksforgeeks.org/complexity-cheat-sheet-for-python-operations/

Time complexity for lookup in dictionary.values() lists vs sets In this case, it searches for each key's list so it didn't help me. Because in my case, all Dict's values will be a single integer.

Q(1): Is it O(1) or O(n) for Dict.values()?

Dict = {1:10,2:20,3:30,4:40}
if 10 in Dict.values():
    print("YES")

Q(2): In python is it possible to get key by supplying value?[if the supplied value comes multiple times in Dict.values() I would like to get all corresponding keys]

Dict = {1:10,2:20,3:30,4:40}
value = 20

I want to find key=2 by this value. Is it possible with O(1), because in O(n) I have to check for all key's value!!!

Upvotes: 1

Views: 2136

Answers (1)

leaf_soba
leaf_soba

Reputation: 2518

Q(1)：I think it is O(1)

edit:I was wrong.It is O(n).Thanks to @Roy Cohen and @kaya3.

test code:

import timeit
def timeis(func):
    def wrap(*args, **kwargs):
        start =  timeit.default_timer()
        result = func(*args, **kwargs)
        end =  timeit.default_timer()
        print(func.__name__, end-start)
        return result
    return wrap

import random
@timeis
def dict_values_test(dic,value):
    return value in dic.values()

tiny_dic = {i : 10*i for i in range(1000)}
value = random.randint(1,1000)
dict_values_test(tiny_dic,value)
small_dic = {i : 10*i for i in range(1000000)}
value = random.randint(1,1000000)
dict_values_test(small_dic,value)
big_dic = {i : 10*i for i in range(100000000)}
value = random.randint(1,100000000)
dict_values_test(big_dic,value)

result:

dict_values_test 2.580000000002025e-05
dict_values_test 0.015847600000000073
dict_values_test 1.4836825999999999

Q(2):

code:

def find_key_by_value(dic,find_value):
    return [k for k,v in dic.items() if v == find_value]
        
dic = {1:10,2:20,3:30,4:40,5:40}
print(find_key_by_value(dic,40))

result:

[4, 5]

Upvotes: 1

Related Questions