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