Efficient coding considered harmful?

[Rob Carriere]

In article <1718 at garth.UUCP> smryan at 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