What's the time complexity of adding a new key-value pair like so:
d = dict()
d.update({'key':'value'})
Can't find it in here https://wiki.python.org/moin/TimeComplexity
What's the time complexity of adding a new key-value pair like so:
d = dict()
d.update({'key':'value'})
Can't find it in here https://wiki.python.org/moin/TimeComplexity
The update function for dictionaries in Python can be called a few different ways. The first is as a mapping of keys to values followed by optional keyword arguments. The second way is a list of tuples followed by optional keyword arguments. The third is as a series of keyword arguments. We can see these function stubs in builtins.pyi:
@overload
def update(self, __m: Mapping[_KT, _VT], **kwargs: _VT) -> None: ...
@overload
def update(self, __m: Iterable[Tuple[_KT, _VT]], **kwargs: _VT) -> None: ...
@overload
def update(self, **kwargs: _VT) -> None: ...
and this more practical example:
d_obj = dict()
d_obj.update({'a':1},b=2)
d_obj.update([('c',3)],d=4)
d_obj.update(e=5)
print(d_obj)
For each of these implementations Python will iterate through each argument passed in and check if the key is in the dictionary in constant time. If the key is in the dictionary the function will set the key to its new value. If it is not then the function will add the key to the dictionary and set its value. Since all of these adding and setting operations can be assumed to be done in constant time we can assume each individual item passed in to update()
is completed in constant time thus we get O(1 * n) where n is equal to the number of individual key-value pairs passed in to update()
. Thus the time complexity of the update function is O(n).
python dict is hash table
Below is table of "Time complexity in big O notation" (taken from the same link above)
Algorithm Average Worst case
Space O(n)1 O(n)
Search O(1) O(n)
Insert O(1) O(n)
Delete O(1) O(n)
Since "Set item" is listed as O(1)
average case and O(n)
worst case, I believe you can assume this is also the complexity for update()
.