Lists, tuples and dicts (and maybe strings?) know how long they are, so
len() takes essentially constant time.

Custom classes are free to define __len__ anyway they like.

class MyList(list):
    """Just like the built-in list, but stupider."""
    def __len__(self):
        # Untested, for obvious reasons.
        import random
        import sys
        while True:
            guess = random.randrange(0, sys.maxint)
            count = 0
            for i in self:
                count += 1
            if count == guess:
                return count

Caching __len__ is left as an exercise to the reader...