array, list, performance...
John Machin
sjmachin at lexicon.net
Fri Jun 7 22:06:52 EDT 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