[Tutor] Counting # of dictionary keys

Tim Peters tim.one@comcast.net
Wed Apr 16 12:54:07 2003

[Dana Larose]
> I'm curious about the following:
> >>> len(your_dict)
> What is the complexity of this operation?  Does it run in time O(1) or
> O(n)?

This is the implementation today (in dictobject.c):

static int
dict_length(dictobject *mp)
	return mp->ma_used;

So it's constant-time today, and has been in the C implementation of Python
since the beginning.  The language reference manual doesn't guarantee this,
but it's unlikely to change.