array, list, performance...

John Machin sjmachin at lexicon.net
Sat Jun 8 04:06:52 CEST 2002


Ype Kingma <ykingma at accessforall.nl> wrote in message news:
> Multiplying the list's size by a constant factor when necessary would 
> give O(log(len(li)) * len(li)) behaviour

I'm not sure where you get this from. Here's my take:

The theoretical amortised cost is O(N), not O(log(N)*N), where N is
the utimate size of the list.

Let F be the factor by which the list size is expanded when necessary.
Let e be the number of expansions required to grow to size N.
F**e is O(N).

The ith expansion involves fiddling with O(F**i) elements, with O(1)
cost each. The total of this over e expansions is O(F**e). As above,
F**e is O(N).

The O(1) cost each is theoretical. The operating system's memory
allocator may exhibit worse-than-linear behaviour.

Cheers,
John



More information about the Python-list mailing list