1

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

Leonardus Chen
  • 1,103
  • 6
  • 20

3 Answers3

4

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).

0x263A
  • 1,807
  • 9
  • 22
  • 1
    Note that `n` in this analysis is the number of key/value pairs to add, not the size of the dict itself. I think you said this, but just want to emphasize it. – Code-Apprentice Sep 08 '21 at 21:51
  • 1
    Yes, I stated it here "where n is equal to the number of individual key-value pairs passed in to update()", but it is worth emphasizing as that phrasing is a bit unclear. – 0x263A Sep 08 '21 at 21:55
  • Right, so it doesn't matter whether or not the key is already in the dictionary - since we assume adding a new key to a dictionary is O(1) ? Follow-up question, why does this website says the worst case of `SetItem[1]` is `O(n)` then? (I presume `n` here is the size of dictionary) – Leonardus Chen Sep 09 '21 at 11:17
  • 1
    Python's dict is underpinned by a data structure called a hash table. There are properties of this ds that make it such that the worst case for insertion is O(n). It's a bit of a lengthy answer for a comment, but see [here](https://stackoverflow.com/questions/9214353/hash-table-runtime-complexity-insert-search-and-delete) for more information on this and [here](https://stackoverflow.com/questions/730620/how-does-a-hash-table-work) for more on hash tables. @LeonardusChen – 0x263A Sep 09 '21 at 12:36
1

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)

balderman
  • 22,927
  • 7
  • 34
  • 52
  • This is the same information already provided in the question's link. – MisterMiyagi Sep 08 '21 at 15:16
  • 2
    Yes - but OP was not able to find the "Time complexity in big O notation" table there and my answer pointed to the table and to the answer. – balderman Sep 08 '21 at 15:17
  • As far as I understood the question the problem isn't an inability to scroll down the page but rather that ``dict.update`` and ``dict.__setitem__``/SetItem/insert are distinct operations and only the latter is listed. The information shown here also only covers ``dict.__setitem__``/SetItem/insert. – MisterMiyagi Sep 08 '21 at 15:47
  • So it doesnt matter whether or not "key" is already in dict.keys ? (i.e., updating value of existing key vs inserting a new key) – Leonardus Chen Sep 08 '21 at 17:55
  • @LeonardusChen Both ``dict.update(…)`` and ``dict[…] = …`` can insert and update pairs. – MisterMiyagi Sep 08 '21 at 18:50
0

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().

Code-Apprentice
  • 81,660
  • 23
  • 145
  • 268