|
![](/i/fill.gif) |
Warp wrote:
> Darren New <dne### [at] san rr com> 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
|
![](/i/fill.gif) |