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

[process]

Python uses arrays for lists right?

def quicksort(lista):
if lista == []:
lista
else:
return quicksort([x for x in lista[1:] if x < lista[0]]) +
[lista[0]] + \
quicksort([x for x in lista[1:] if x >= lista[0]])

or

def quicksort(lista):
if len(lista) == 0
lista
else:
return quicksort([x for x in lista[1:] if x < lista[0]]) +
[lista[0]] + \
quicksort([x for x in lista[1:] if x >= lista[0]])

wait first one raises TypeError unsupported operand types.

 

[Fredrik Lundh]

Python uses arrays for lists right?

len is O(1). for other operations, see

http://effbot.org/zone/python-list.htm#performance

> def quicksort(lista):
> if lista == []:
> lista

better make that:

def quicksort(lista):
if not lista:
return lista
...

</F>

 

[process]

ok but if len is O(1) then it doesnt matter? compared to

if not lista:
return []

i mean.

 

[Fredrik Lundh]

ok but if len is O(1) then it doesnt matter? compared to

if not lista:
return []

what doesn't matter?

</F>

 

[skip]

>> 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.:
... if not a: return []
... 2 0 LOAD_FAST 0 (a)
3 JUMP_IF_TRUE 5 (to 11)
6 POP_TOP
7 BUILD_LIST 0
10 RETURN_VALUE 12 LOAD_CONST 0 (None)
15 RETURN_VALUE ... if not len(a): return []
... 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 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