Cost of len() function
It's O(1) (constant time, not depending of actual length of the element - very fast) on every type you've mentioned, plus set
and others such as array.array
.
Calling len() on those data types is O(1) in CPython, the most common implementation of the Python language. Here's a link to a table that provides the algorithmic complexity of many different functions in CPython:
All those objects keep track of their own length. The time to extract the length is small (O(1) in big-O notation) and mostly consists of [rough description, written in Python terms, not C terms]: look up "len" in a dictionary and dispatch it to the built_in len function which will look up the object's __len__
method and call that ... all it has to do is return self.length