Show the result of the following sequence of instructions: union(1,2), union(3,4), union(3,5), union(1,7), union(3,6), union(8,9), union(1,8), union(3,10), union(3,11), union(3,12), union(3,13), union(14,15), union(16,0), union(14,16), union(1,3), union(1,14) when the union operations are performed according to below algorithm and write the complexity of each algorithm:
1.Quick Find
2.Quick Union
3.Weighted quick union
1. Quick Find
union(1,2)
union(3,4)
union(3,5)
union(1,7)
union(3,6)
union(8,9)
union(1,8)
union(3, 10)
union(3, 11)
union(3, 12)
union(3, 13)
union(14, 15)
union(16, 0)
union(14, 16)
union(1, 3)
union(1, 14)
Time Complexity : O(n)
2. Quick union
union(1,2)
union(3,4)
union(3, 5)
union(1, 7)
union(3, 6)
union(8, 9)
union(1, 8)
union(3, 10)
union(3, 11)
union(3, 12)
union(3, 13)
union(14, 15)
union(16, 0)
union(14, 16)
union(1, 3)
union(1, 14)
Time Complexity: O(n)
3. Weighted Quick Union
union(1, 2)
union(3, 4)
union(3, 5)
union(1, 7)
union(3, 6)
union(8, 9)
union(1, 8)
union(3, 10)
union(3, 11)
union(3, 12)
union(3, 13)
union(14, 15)
union(16, 0)
union(14, 16)
union(1, 3)
union(1, 14)
Time Complexity:
O(logn)
NOTE: Although the answers of (2) and (3) might look similar, their algorithms are significantly different. In Weighted Quick Union, the root of the tree with a smaller size is always added to the root of the tree with larger size. This ensures that the height of the tree is minimized and the worst case time complexity is thus reduced to O(logn). No such checking is available in the algorithm of (2), i.e. Quick Union, whose time complexity in the worst case is O(n).
1. Quick Find
union(1,2)
union(3,4)
union(3,5)
union(1,7)
union(3,6)
union(8,9)
union(1,8)
union(3, 10)
union(3, 11)
union(3, 12)
union(3, 13)
union(14, 15)
union(16, 0)
union(14, 16)
union(1, 3)
union(1, 14)
Time Complexity : O(n)
2. Quick union
union(1,2)
union(3,4)
union(3, 5)
union(1, 7)
union(3, 6)
union(8, 9)
union(1, 8)
union(3, 10)
union(3, 11)
union(3, 12)
union(3, 13)
union(14, 15)
union(16, 0)
union(14, 16)
union(1, 3)
union(1, 14)
Time Complexity: O(n)
3. Weighted Quick Union
union(1, 2)
union(3, 4)
union(3, 5)
union(1, 7)
union(3, 6)
union(8, 9)
union(1, 8)
union(3, 10)
union(3, 11)
union(3, 12)
union(3, 13)
union(14, 15)
union(16, 0)
union(14, 16)
union(1, 3)
union(1, 14)
Time Complexity:
O(logn)
NOTE: Although the answers of (2) and (3) might look similar, their algorithms are significantly different. In Weighted Quick Union, the root of the tree with a smaller size is always added to the root of the tree with larger size. This ensures that the height of the tree is minimized and the worst case time complexity is thus reduced to O(logn). No such checking is available in the algorithm of (2), i.e. Quick Union, whose time complexity in the worst case is O(n).
Show the result of the following sequence of instructions: union(1,2), union(3,4), union(3,5), union(1,7), union(3,6), union(8,9), union(1,8),...