Time Complexity of Python dictionary len() method

Question

Example:

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

What is the time complexity of len(a) ?

Answer 1

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)

Answer 2

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.