Clicker Questions - 11-Disjoint
In these questions, use alpha() for the inverse Ackerman function.
Question 1: Suppose I’m using Union By Height and I have a disjoint set instance with $n$ elements. What is the running time of performing $m$ Union operations, where $m < n$?
Answer
This is $O(m)$, because union operations are $O(1)$.Question 2: Suppose I’m using Union By Rank with Path Compression, and I have a disjoint set instance with $n$ elements. What is the running time of performing $m$ Union and $m$ Find operations, where $m < n$?
Answer
The unions are $O(1)$ each, and the finds are $O(\text{alpha}(n))$. Since that second function is bigger than the first, our running time only has to include the second. The answer is $O(m \text{ alpha}(n))$.Question 3: Suppose that I have two STL sets, both of size $n$. What is the running time of creating an STL set that is their union?
Answer
You create this set by copying one set, and then traversing the second set and inserting each element. The copy is $O(n)$, and the traversal/insertion is $O(n \; log(2n))$. That is $O(n \; log \; n)$.Question 4: Suppose I’m using Union By Rank with Path Compression. What is the minimum number of elements that I need to have to create a set whose rank is 5?
Answer
First off, in Union By Rank with Path Compression, "rank" is equivalent to "height" in Union By Height. So this question is the same as asking, "Suppose I'm using Union By Height. What is the minimum number of elements that I need to have to create a set whose height is 5."So, let's answer a general question: Define $mh(n)$ be the minimum number of elements in a set whose height is $n$. We start with $n=1$. Clearly, that is 1. Now, the only time that you increase the height of a set is when you union together two sets with the same height. So, you can make a set with height $n$ and $mh(n)$ elements by unioning two sets with $mh(n-1)$ elements. Given that:
- $mh(2) = 2 \times mh(1) = 2$
- $mh(3) = 2 \times mh(2) = 4$
- $mh(4) = 2 \times mh(3) = 8$
- $mh(5) = 2 \times mh(4) = 16$
Question 5: Suppose I’m using Union By Size. What is the minimum number of elements that I need to have to create a set whose height is 5? (Note, I’m saying “height”, and not “size”).
Answer
Now, Define $msh(n)$ be the minimum number of elements in a set, created with Union By Size, whose height is $n$. Again, $msh(1)$ $= 1$. Now, suppose you have two sets, $a$ and $b$, and you union them. The only time that this increases the height of either is when the height of $b$ is greater than or equal to the height of $a$, and the size of $a$ is greater than or equal to the size of $b$. So, to minimize $msh(n)$, you need to union $a$ and $b$, where $b$ is of height $(n-1)$, and therefore has $msh(n-1)$ elements, and $a$'s size is greater than or equal to $b$'s size. Therefore, $a$ has $msh(n-1)$ elements, too.So $msh(n) = 2 \times msh(n-1)$, and like question 1, the answer is 16. You should note that the logic to derive the two is different.