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

[Marc 'BlackJack' Rintsch]

On Thu, 11 Sep 2008 02:23:43 -0700, process wrote:

> Python uses arrays for lists right?

`len()` on `list` objects is O(1).

> 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.

Both do because `None` + `list` doesn't make sense.  You should actually 
``return`` the `lista` in the ``if`` branch instead of just lookup the 
object for that name and then do nothing with it.

Shorter alternative:

    if not lista:
        return []

Empty lists are considered `False` in a boolean test.

Ciao,
	Marc 'BlackJack' Rintsch