I am learning Python and wondering what would be the time complexity of dictionary on all operation(Copy[2], Get Item, Set Item[1], Delete Item, Iteration[2]). If I use tuple values as a key in the dictionary. Can someone please throw some light ?
Here's the sample code.
keys = ("Name", "age", "height")
dog = {keys[0]: "labrador", keys[1]: 2, keys[2]: 3}
Based on this link:
Except copy or iteration, dict have a complexity of O(1) or worse case O(n).
For copy or iteration, it's logical that it is O(n) as there is n elements that you can access in O(1) complexity.
As commented by Laurent, all dictionnary are "stored" based on the hash of the key (link). In some cases, it can happens that 2 keys have the same hash (collision). In such cases, I imagine, it end up in the "Amortized Worst Case" as it's gonna check all keys as is and not the hash. You can also find more information about the build of dictionnaries on this topic.
In addition, for copy and iterations, you should consider the biggest n reach in the dictionnary. If you fill 10000 entries then remove 9990 and do a copy, you should consider 10000 elements and not 10.
EDIT 1: Test times based on key time
You can test the time based on key type with following code :
import timeit
def f1():
a = {}
for i in range(1000):
a[i] = i
return a
def f2():
a = {}
for i in range(1000):
a[str(i)] = i
return a
def f3():
a = {}
for i in range(1000):
a[(i, i)] = i
return a
def f4():
a = {}
for i in range(1000):
a[(str(i), str(i))] = i
return a
print(timeit.timeit("f1()", number = 1000, setup="from __main__ import f1")) # => 0.0541156338055877
print(timeit.timeit("f2()", number = 1000, setup="from __main__ import f2")) # => 0.2492961917066741
print(timeit.timeit("f3()", number = 1000, setup="from __main__ import f3")) # => 0.09082684668080204
print(timeit.timeit("f4()", number = 1000, setup="from __main__ import f4")) # => 0.4479192082498416
Unfortunately, you cannot compare them 1 by 1 as f2 and f4 use str() function which slow down the function but you can at least see that tuple is slower than simple string or integer. Nevertheless you can estimate with the following code the time used to convert to str()
def f5():
for i in range(1000):
str(i)
print(timeit.timeit("f5()", number = 1000, setup="from __main__ import f5"))
And this is evaluate to 0.1645s. Without this time is f2 and twice in f4 you have :
0.08614475546254619s for f2
0.12553885821459693s for f3
This gives you some idea about the time to create dict based on the key style. You can do the same to test time access but if hashes doesn't collide, time should be the same no matter the key style.
You can also take a look to this video I found tonight
I hope it helps,
