On Wed, 26 Apr 2006, Rob wrote:
On Wed, Apr 26, 2006 at 11:21:19PM -0400, Rob wrote:
both a and bmare in the[1] set, even though hash(a) == hash(b). This would
use space O(k+k*log m ) and a running time that is a pain in the ass
Stupid terminal fuckups... that is supposed to read "a and b are in the
set" and below that "O(m+k*log m)[1]"; my term was screwed up so my edit
ended up off by one line :-(
Actually, wait a second. To look up wether an integer has been picked
already, your method uses O(log(n)) to compute the hash and O(log(i/k)) to
search the binary tree at that node, for O(log(n*i/k)) overall. But using
only one big tree gives O(log(i)), which is better unless k > n (but if k
n hashing is meaningless anyway). ISTM that hashing is only worthwile if
you can calculate the hash faster than O(log(k)) where k is the number of
buckets... this means only hashes in constant time relative to k, m and n
are any good.
Alexey
