Nick Coghlan writes:
len(container) by contrast, is an O(1) operation - the time it takes is independent of the length of the input.
I think a better way to put this is that len(container) is *designed* to return an attribute that is computed as the container is (de-) populated, so is O(1) for access. The fact that some "containers" that wrap external objects (eg, Scott's example of Maildir) have to use O(N) algorithms for accuracy (since these objects are shared with other processes) doesn't really contradict the argument from "design", it just suggests one should be careful when giving those containers a __len__. Also, at least for the Maildir example, len(maildir) doesn't access the Maildir; it accesses the OS's directory listing facility, which has a "C" so small that I suppose it's effectively O(1) compared to sum(1 for m in maildir). I don't know if that (pseudo?) logic applies to other such examples, though.