1

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!!!

Aayush Scet
  • 37
  • 1
  • 6
  • I think both your examples are `O(n)`, but the call itself `dict.values()` is `O(1)` due to delayed execution. – Roy Cohen May 13 '21 at 07:14
  • 1
    If you want to test if a value is present, and get the key associated with a value, then your dictionary is back-to-front. Make it `{10: 1, 20: 2, 30: 3, 40: 4}` instead. – kaya3 May 13 '21 at 07:15
  • @RoyCohen First you said it is O(n) and then you said Dict.values() is O(1) because of delayed execution[Then what should I assume? O(1) or O(n)?] – Aayush Scet May 13 '21 at 07:17
  • @kaya3 Yeah that's true. So I assume, answer is no for my case. – Aayush Scet May 13 '21 at 07:19
  • 1
    @AayushScet The call `dict.values()` itself is `O(1)`, but when you use the object returned by `dict.values()` it's usually `O(n)` (depends on what you're doing). – Roy Cohen May 13 '21 at 07:20

1 Answers1

1

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]
leaf_yakitori
  • 2,232
  • 1
  • 9
  • 21
  • 1
    The `1000` is always the 100th value in the dict. The fact that the times are all 0 means that the algorithm shortcircuts, not that it's `O(1)`. – Roy Cohen May 13 '21 at 07:37
  • 1
    Please use `timeit`, not `time`, for benchmarking Python code, especially single operations. – kaya3 May 13 '21 at 17:06