Home Original page

Algorithmic complexity of len (list)?

Sam Holden sholden at flexal.cs.usyd.edu.au
Fri Jul 2 19:47:30 EDT 2004 
On Fri, 02 Jul 2004 19:18:20 -0400, Roy Smith <roy at panix.com> 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):
    lists.append(range(1,10**len_power))


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

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