Algorithmic complexity of len (list)?
sholden at flexal.cs.usyd.edu.au
Sat Jul 3 01:47:30 CEST 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:
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).
More information about the Python-list