CODEWITHSUNDEEP
pythondictionarytime-complexity
Yiling Liu
Yiling Liu

Reputation: 686

Time Complexity of Python dictionary len() method

Example:

a = {a:'1', b:'2'}
len(a)

What is the time complexity of len(a) ?

Upvotes: 10

Views: 4753

Answers (2)

Yiling Liu
Yiling Liu

Reputation: 686

According to this page:

Time Complexity: O(1) – In Python, a variable is maintained inside the container(here the dictionary) that holds the current size of the container. So, whenever anything is pushed or popped into a container, the value of the variable is incremented(for the push operation)/decremented(for the pop operation). Let’s say, there are 2 elements already present in a dictionary. When we insert another element in the dictionary, the value of the variable holding the size of the dictionary is also incremented, as we insert the element. Its value becomes 3. When we call len() on the dictionary, it calls the magic function len() which simply returns the size variable. Hence, it is O(1) operation.

Space Complexity: O(1) – Since there’s only a single variable holding the size of the dictionary, there’s no auxiliary space involved. Hence the space complexity of the method is O(1) too.

Upvotes: 7

donkopotamus
donkopotamus

Reputation: 23216

Inspecting the c-source of dictobject.c shows that the structure contains a member responsible for maintaining an explicit count (dk_size)

layout:
+---------------+
| dk_refcnt     |
| dk_size       |
| dk_lookup     |
| dk_usable     |
| dk_nentries   |
+---------------+
...

Thus it will have order O(1)

Upvotes: 16

Related Questions