Complexity of reallocating storage (was users command crap)

[David Chase]

brnstnd at kramden.acf.nyu.edu (Dan Bernstein) writes:
>Any single-pass ``users'' has to either use quadratic time or be a rude
>abuser of resources. Why not use two passes and be done with it?

No reason not to do that, and that's not what I was arguing (hard to
imagine rudely abusing resources on a machine large enough to support
enough users that the users command would rudely abuse resources, but
so it goes).  Maybe this is a sensible tradeoff on the machines that
you use.

However, you said that quadratic time was "required".  No "or abuse
resources" to qualify that statement.  I'm interested in knowing how
you arrived at this conclusion, since, in fact, it is false.  I figure
you'll find some way to redefine your way out of this blunder; just
wanted to be sure that you did in it in public so that all could see
that you aren't the infallible "mathematician" that you claim you are.

NB -- doubling yields peak waste of 66% (N bytes in old, 2N in new,
copy not yet made, only N useful bytes), not 50%.  See?  You didn't
even get that right.  Be more careful when you post, ok?  Takes
people's time to read these things.

Yours,

David Chase
Sun Microsystems
(and member of the Dan Bernstein USENET fan-the-flames club)