I was reading about the famous union-find problem, and the book was saying: "either the find or the union will take O(n)
time, and the other one will take O(1)
...."
But what about using bit strings to represent the set?
Then both union (using bit OR) and find (iterating through set lists checking the corresponding bit is 1
) will take O(1)
..
What is wrong with that logic?
With a bitfield
or
on two native integers but if n is large you obviously cannot use builtin types.Also, a bitfield is not really suited for arbitrary sets. For example if you have a set that can contain any 32bit integer, you need a bitfield with a size of 4G/8=0.5G.