Path: utzoo!attcan!uunet!seismo!sundc!pitstop!sun!oliveb!Ozona!chase
From: chase@Ozona.orc.olivetti.com (David Chase)
Newsgroups: comp.lang.c
Subject: Re: Efficient coding considered harmful?
Message-ID: <31898@oliveb.olivetti.com>
Date: 3 Nov 88 06:54:32 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>
Sender: news@oliveb.olivetti.com
Reply-To: chase@Ozona.UUCP (David Chase)
Organization: Olivetti Research Center, Menlo Park, CA
Lines: 22

In article <1709@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes:
>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.

First estimate is size k, too small, so we double it (etc) finally
reaching size k*2^n.  How many bytes have we copied?  We've copied

        k + k * 2 + ... + k * 2^(n-1) = k * (2^n - 1).

This is linear in the final size.  We also did n allocations, but n is
proportional to the log of the size (and bounded by 32 on most
machines that I use) so we don't worry about the time spent
allocating.

"Efficient coding" is indeed harmful if you can't figure out the
complexity of your algorithms.

David