CODEWITHSUNDEEP
pythonpython-3.xdictionarytime-complexityasymptotic-complexity
Drathier
Drathier

Reputation: 14519

What is the complexity of calling of dict.keys() in Python 3?

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.

Upvotes: 6

Views: 1781

Answers (1)

Alex Riley
Alex Riley

Reputation: 176750

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.

Upvotes: 8

Related Questions