Algorithmic complexity of len (list)?

Sam Holden sholden at
Sat Jul 3 01:47:30 CEST 2004

On Fri, 02 Jul 2004 19:18:20 -0400, Roy Smith <roy at> wrote:
> Is the length of a list stored in the object, or does len() have to 
> count the elements each time you call it?  In other words, is len (list) 
> O(1) or O(n)?

I'd assume O(1), and the following seems to verify it:

import time
lists = []
for len_power in range(1,8):

for l in lists:
    start = time.time()
    length = len(l)
    end = time.time()
    print "%d\t%f" % (length, end-start)

I'm sure there's a python library that does a much better
job of determining average runtimes, but for this case if
it was O(n) is should show up pretty quick in the output

The existance of negative indexing strongly implies O(1) as 
well, as does the existance of bounds checking when
accessing (rather than random core dumps).

Sam Holden

More information about the Python-list mailing list