len() on mutables vs. immutables

[Nick Cash]

> I'm curious as to the implementation (I'd be happy to dig through the
> source, just don't have the time right now). I've seen various
> implementations across interpreters in the past (some which have been
> rather shocking) and I'd like to get some insight into Python (well,
> CPython at this point anyway).
> 
> When len() is called passing an immutable built-in type (such as a
> string), I'd assume that the overhead in doing so is simply a function
> call and there are no on-call calculations done. Is that correct?
> 
> I'd also assume that mutable built-in types (such as a bytearray) would
> cache their size internally as a side effect of mutation operations. Is
> that correct? If so, is it safe to assume that at least all built-in
> types observe this behavior, or are there some that incur an O(n) cost
> on every len() call?

It appears that list has len() complexity of O(1)
source: http://wiki.python.org/moin/TimeComplexity
It may be worth mentioning that lists in Python are implemented using arrays instead of linked lists.

It's reasonable to assume that other built-in collection types would be similar, though I don't see anything explicitly saying so for bytearray.

-Nick Cash