Xref: utzoo comp.bugs.4bsd:1680 comp.std.c:4198 comp.lang.c:35539
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!julius.cs.uiuc.edu!apple!netcom!amdcad!sun!exodus!rbbb.Eng.Sun.COM!chased
From: chased@rbbb.Eng.Sun.COM (David Chase)
Newsgroups: comp.bugs.4bsd,comp.std.c,comp.lang.c
Subject: Complexity of reallocating storage (was users command crap)
Summary: Cheaper than you think?
Message-ID: <6662@exodus.Eng.Sun.COM>
Date: 25 Jan 91 23:36:36 GMT
References: <1991Jan24.060707.22566@tkou02.enet.dec.com> <22870@well.sf.ca.us> <22311:Jan2502:34:1191@kramden.acf.nyu.edu>
Sender: news@exodus.Eng.Sun.COM
Followup-To: comp.bugs.4bsd
Organization: Sun Microsystems, Mt. View, Ca.
Lines: 20

brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
>Now you can talk all you want about reallocating memory (btw, there's no
>safe way to use realloc(), but you knew that) to read in as many users
>as possible. I'll skip the comments about a quadratic time
>requirement...

I'll bite -- are you saying that reallocating memory to obtain a
larger array and copying old into new always takes ("requires")
quadratic time?  (Quadratic time in what?  I assume number of array
elements.) I always double the size when I do this, by the way.

1 + 2 + 4 + 8 + ... + 2^N = 2 * (2^N) - 1, which is linear in 2^N,
which is the number of array elements.

But I'm sure you knew that, so you must have been talking about
something else.  What were you talking about?  Inquiring minds want to
know.

David Chase
Sun Microsystems