Union-Find algorithm

Question

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?

Answer 1

With a bitfield

• union is going to be O(n). You assume that you can do a simple bit or on two native integers but if n is large you obviously cannot use builtin types.
• finding is going to be O(1). You don't have to iterate, you know the exact location of the bit.

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.

Answer 2

Both operations can be done in amortized time of O(Alpha(n)), where Alpha is an inverse of the Ackermann function (grows very slowly). You have to represent the problem as a forrest. Choose a representative of some subgraph (tree node) and the union operation will merge the trees (hang the smaller tree below the root of the higher). The union operation simply traverses to the root AND shorthens the traversed path (hangs the searched element (possibly all traversed elements) below the root).