Complexity of reallocating storage (was users command crap)

[David Chase]

brnstnd at kramden.acf.nyu.edu (Dan Bernstein) writes:
>Now you can talk all you want about reallocating memory (btw, there's no
>safe way to use realloc(), but you knew that) to read in as many users
>as possible. I'll skip the comments about a quadratic time
>requirement...

I'll bite -- are you saying that reallocating memory to obtain a
larger array and copying old into new always takes ("requires")
quadratic time?  (Quadratic time in what?  I assume number of array
elements.) I always double the size when I do this, by the way.

1 + 2 + 4 + 8 + ... + 2^N = 2 * (2^N) - 1, which is linear in 2^N,
which is the number of array elements.

But I'm sure you knew that, so you must have been talking about
something else.  What were you talking about?  Inquiring minds want to
know.

David Chase
Sun Microsystems