Q)a)(T/F) The running time of the combined union-by-rank and path-compression he
ID: 3712542 • Letter: Q
Question
Q)a)(T/F) The running time of the combined union-by-rank and path-compression heuristic is O(m×?(m,n)) for m disjoint-set operations and n elements. In practice, this run-time is as good as linear time complexity.
b)(T/F) In the linked list representation of disjoint sets, we could save tail pointer of a linked list by making the tail of the linked list as the representative. To reach to the tail of the linked list, we could use the head pointer to get the head of the linked list and use the representative pointer to get to the tail. To implement weighted-union heuristic, we insert the shorter list after the head of the longer list. The update of the representative pointers in the shorter list is done by traversing the list to the end. Then, make the tail of the shorter list points to the second element of the longer list. This scheme without tail pointer performs the weighted-union heuristics correctly with the same run-time complexity
Explanation / Answer
<A> True
Runtime is as good as linear time complexity
b) <>True
?We will achieve the same time complexity
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.