Possible Duplicate:
Cost of len() function
Does len() iterate over the objects in a list and then return their count? Thus giving it a O(n).
Or....
Does a python list keep a count of any objects that are appended to it and removed from it and then simply return this "count" when len() is called? Thus giving it O(1).
Best Answer
A Python list knows its own length; len takes O(1) time. Lists are actually arrays, not linked lists as in Lisp, where length takes linear time.
For all built-in objects that define __len__(), it will be O(1). If you implement __len__() for your own objects, it might be anything.