What is the big-o notation for the `len()` function in Python? [duplicate]

Question

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).

Answer 1

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.

Answer 2

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.