Path: utzoo!yunexus!geac!syntron!jtsv16!uunet!lll-winken!arisia!quintus!ok
From: ok@quintus.uucp (Richard A. O'Keefe)
Newsgroups: comp.lang.c
Subject: Re: Efficient coding considered harmful?
Message-ID: <618@quintus.UUCP>
Date: 2 Nov 88 08:38:33 GMT
Article-I.D.: quintus.618
References: <3105@hubcap.UUCP> <34112@XAIT.XEROX.COM> <1700@dataio.Data-IO.COM> <8630@smoke.ARPA> <1704@dataio.Data-IO.COM> <119@twwells.uu
Sender: news@quintus.UUCP
Reply-To: ok@quintus.UUCP (Richard A. O'Keefe)
Organization: Quintus Computer Systems, Inc.
Lines: 13

In article <1709@garth.UUCP> smryan@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.