Path: utzoo!utgpu!attcan!uunet!seismo!sundc!pitstop!sun!decwrl!labrea!sri-unix!garth!smryan
From: smryan@garth.UUCP (Steven Ryan)
Newsgroups: comp.lang.c
Subject: Re: Efficient coding considered harmful?
Message-ID: <1718@garth.UUCP>
Date: 2 Nov 88 22:57:43 GMT
References: <3105@hubcap.UUCP> <34112@XAIT.XEROX.COM> <1700@dataio.Data-IO.COM> <8630@smoke.ARPA> <1704@dataio.Data-IO.COM> <119@twwells.uucp> <342@auspex.UUCP> <1709@garth.UUCP> <618@quintus.UUCP>
Reply-To: smryan@garth.UUCP (Steven Ryan)
Organization: INTERGRAPH (APD) -- Palo Alto, CA
Lines: 8

>[the context is realloc()]
>
>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.

However, this makes the space cost O(1.5**n), exponential.