I recently began focusing on the intricacies of Python dictionaries. However, as I began to think a little deeper about the data structure, I encountered several questions––ones that I am struggling to find clear answers for:
What is the time and auxiliary space complexities of .values(), .items(), and .keys()? I have been under the impression that, since they are view objects, they neither require additional space nor additional time to retrieve. In this way, they almost act like pre-set (but dynamic) attributes.
Suppose we had the function foo below, which takes a single input dictionary d:
def foo(d):
bar = d.values()
While this function has space complexity of O(N), where N is the number of entries in the dictionary, what is the auxiliary space complexity of this function? In other words, does d.values() consume additional space? If it does, the auxiliary space of this function would be O(N). If not, the auxiliary space is O(1).
Likewise, does this function have a time complexity of O(N), where N is the number of entries in the dictionary, or does it run in O(1) time?
In essence, I am trying to understand the mechanics of a view object. Thanks!
They all take O(1) time and space. They just return a small view object that internally references the dict, so when you do something with the view object, the view object uses the dict to actually do it.