Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> Amortized O(1) append is only O(1) if you double the size of the array each 
>> time you insert something.
> 
>   There are two errors in that sentence:
> 
> 1) You don't double the size of the array each time you insert something. You
>    do so each time the array gets full.

Yes. Brain-o.

> 2) AFAIK it's not necessary to precisely *double* the size of the array in
>    order to get amortized constant time insertion. It's enough to multiply
>    the size of the array by a constant factor (eg. 1.5).
>    (Although don't quote me on that, as I haven't done the math.)

The amortization is the sum of one over the number of elements you move. And 
yes, I'm pretty sure you're right. Basically, it needs to be a geometric 
progression of expansions that converges, rather than bumping up to (say) 
the next prime number or adding a constant or something.

-- 
   Darren New, San Diego CA, USA (PST)
   I ordered stamps from Zazzle that read "Place Stamp Here".

Post a reply to this message