array, list, performance...

[Ype Kingma]

John Machin wrote:
> 
> 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).

Thanks. I thought each of the e expansions would involve fiddling with
O(N) elements.
Perhaps I should post before my working day instead of after...

Regards,
Ype