Newsgroups: comp.programming
From: hoey@zogwarg.etl.army.mil (Dan Hoey)
Date: 7 Jan 93 17:01:06 GMT
Subject: Re: Locating duplicates

k...@cs.cornell.edu (David Karr) writes:

>A shortcoming of course is that the running-time analysis is valid
>only if you can repeatedly allocate large amounts of zeroed-out memory
>in a small (essentially constant) time.

You can actually skip the zeroing out at a cost of a constant factor
at access time.  It's well-known; email me if you're interested.

There's a known linear-time solution for the element uniqueness
problem on the real-ram-with-floor model (none of this bogus 32-bit
integer restriction) that uses a kind of hash table in this way.  It
was in JACM in the seventies, if I recall.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil