Path: utzoo!utgpu!attcan!uunet!seismo!sundc!pitstop!sun!amdcad!ames!claris!apple!desnoyer
From: desnoyer@Apple.COM (Peter Desnoyers)
Newsgroups: comp.lang.c
Subject: Re: Efficient coding considered harmful?
Message-ID: <19910@apple.Apple.COM>
Date: 3 Nov 88 17:45:04 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> <1718@garth.UUCP>
Organization: Apple Computer Inc, Cupertino, CA
Lines: 13

In article <1718@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes:
>>[the context is realloc()]
>>
>>Not so.  The standard technique is to increase the size by a MULTIPLICATIVE
>>factor... I tend to use 1.5 ...
>>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.

No, max size <= 1.5N = O(N). There's a big difference between linear
and exponential.

				Peter Desnoyers