Algorithmic complexity of len (list)?

Aahz aahz at pythoncraft.com
Tue Jul 6 16:04:06 CEST 2004


In article <roy-4C2E61.19182002072004 at reader2.panix.com>,
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)?

Consider that if it weren't, operations such as l.pop() and l[-3:] would
also be O(N)...

(I couldn't resist making a comment because I'm currently using your
.sig. ;-)
-- 
Aahz (aahz at pythoncraft.com)           <*>         http://www.pythoncraft.com/

"Typing is cheap.  Thinking is expensive."  --Roy Smith, c.l.py



More information about the Python-list mailing list