Path: utzoo!utgpu!attcan!uunet!seismo!sundc!pitstop!sun!decwrl!labrea!rutgers!mailrus!cwjcc!tut.cis.ohio-state.edu!accelerator!raksha.eng.ohio-state.edu!rob
From: rob@raksha.eng.ohio-state.edu (Rob Carriere)
Newsgroups: comp.lang.c
Subject: Re: Efficient coding considered harmful?
Message-ID: <976@accelerator>
Date: 4 Nov 88 17:44:10 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>
Sender: news@accelerator
Reply-To: rob@raksha.eng.ohio-state.edu (Rob Carriere)
Organization: Ohio State Univ, College of Engineering
Lines: 22

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, 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.


Would someone explain where I am being dense?  As far as I can see,
you need to realloc 

    ln N
k = -------
    ln 1.5m

times, where m is the size of the initial allocation.  Is this not
O(ln N)?

Rob Carriere