Efficient coding considered harmful?

[Richard A. O'Keefe]

In article <1709 at garth.UUCP> smryan at garth.UUCP (Steven Ryan) writes:
[the context is realloc()]

>It sounds as though someone's guessing what the data structure size should
>be, guesses wrong, and has to increase it. If data structure size keeps
>getting bumped bit by bit until the problem size is finally determined,
>then we've got an O(n) structure which has been copied O(n/increment)=O(n)
>times so that the cost of creating just this structure is O(n**2) so that
>the overall time is quadratic, at best.

Not so.  The standard technique is to increase the size by a MULTIPLICATIVE
factor, not an additive increment.  The best factor is data-dependent; I
tend to use 1.5 because that's what InterLisp used, 2 is pretty popular.
The total cost in this case remains O(N), N being the final size.