Is len O(n) or O(1) ?

[skip at pobox.com]

    >> ok but if len is O(1) then it doesnt matter? compared to
    >> if not lista:
    >>         return []

    >> i mean.

Depends on how often the test is performed, e.g.:

    >>> def f(a):
    ...   if not a:  return []
    ... 
    >>> dis.dis(f)
      2           0 LOAD_FAST                0 (a)
                  3 JUMP_IF_TRUE             5 (to 11)
                  6 POP_TOP             
                  7 BUILD_LIST               0
                 10 RETURN_VALUE        
            >>   11 POP_TOP             
                 12 LOAD_CONST               0 (None)
                 15 RETURN_VALUE        
    >>> def g(a):
    ...   if not len(a): return []
    ... 
    >>> dis.dis(g)
      2           0 LOAD_GLOBAL              0 (len)
                  3 LOAD_FAST                0 (a)
                  6 CALL_FUNCTION            1
                  9 JUMP_IF_TRUE             5 (to 17)
                 12 POP_TOP             
                 13 BUILD_LIST               0
                 16 RETURN_VALUE        
            >>   17 POP_TOP             
                 18 LOAD_CONST               0 (None)
                 21 RETURN_VALUE        

Even though len(a) is O(1) it's going to have a much larger constant
coefficient because of the lookup and call to len().

Skip