Menu
What's the asymptotic complexity of dict.keys() in python?
I found this website but it does not have the answer. I am using Python 3, but I guess this is not version specific.
531
It's complexity is 0(1) in Python 3. x. In Python 2. x, it returns a list so populating it or performing some lookup on it takes 0(n) .
Lookups are faster in dictionaries because Python implements them using hash tables. If we explain the difference by Big O concepts, dictionaries have constant time complexity, O(1) while lists have linear time complexity, O(n).
The methods dict. keys() and dict. values() return lists of the keys or values explicitly. There's also an items() which returns a list of (key, value) tuples, which is the most efficient way to examine all the key value data in the dictionary.
Short answer: worst case it is O(n). But the average case time complexity is O(1).
In Python 3, dict.keys() returns a view object. Essentially, this is just a window directly onto the dictionary's keys. There is no looping over the hashtable to build a new object, for example. This makes calling it a constant-time, that is O(1), operation.
View objects for dictionaries are implemented starting here; the creation of new view objects uses dictview_new. All that this function does is create the new object that points back at the dictionary and increase reference counts (for garbage tracking).
In Python 2, dict.keys() returns a list object. To create this new list, Python must loop over the hashtable, putting the dictionary's keys into the list. This is implemented as the function dict_keys. The time complexity here is linear with the size of the dictionary, that is O(n), since every slot in the table must be visited.
N.B. dict.viewkeys() in Python 2 does the same as dict.keys() in Python 3.
145
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
