Algorithmic complexity of len (list)?

[george young]

On Fri, 02 Jul 2004 19:18:20 -0400
Roy Smith <roy at panix.com> threw this fish to the penguins:

> 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)?

[Python 2.3.3]
timeit.py -s 'l=range(5000)' 'len(l)'
1000000 loops, best of 3: 0.975 usec per loop
timeit.py -s 'l=range(10000)' 'len(l)'
1000000 loops, best of 3: 0.975 usec per loop
timeit.py -s 'l=range(50000)' 'len(l)'
1000000 loops, best of 3: 0.975 usec per loop
timeit.py -s 'l=range(100000)' 'len(l)'
1000000 loops, best of 3: 0.975 usec per loop

Sure looks like O(0) to me.

seems to be the same for strings and tuples.

-- George Young

-- 
"Are the gods not just?"  "Oh no, child.
What would become of us if they were?" (CSL)