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.

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.)

-- 
                                                          - Warp

Post a reply to this message