retagged by
1,245 views
0 votes
0 votes

Suppose we want to extend the union-find data structure to support the operation Reset(c), which takes as input the name of a component c and then breaks up c into singleton components, like MakeUnionFind().

For instance if c = 3 and c currently consists of {1,3,7}, then Reset(c) will produce three components called 1, 3 and 7 consisting of {1}, {3} and {7}, respectively.

Which of the following is correct about the cost of adding Reset(c) to the array and pointer implementations of union-find discussed in the lecture?

  1. Array representation: O(n), Pointer representation: O(n)
  2. Array representation: O(size(c)), Pointer representation: O(n)
  3. Array representation: O(n), Pointer representation: O(size(c))
  4. Array representation: O(size(c)), Pointer representation: O(size(c))
retagged by

1 Answer

0 votes
0 votes

B. Array representation: O(size(c)), Pointer representation: O(n) .…

 

In the array+list representation we have the list of members of c which allows us to update the contents of c in time O(size(c))….

In the tree representation there is no easy way to identify all elements that belong to component c without scanning the entire set, so it takes time O(n).…

 

Answer:

Related questions

0 votes
0 votes
3 answers
1
2 votes
2 votes
1 answer
2
rsansiya111 asked Dec 8, 2021
833 views
Suppose we do merge sort with a three-way split: divide the array into 3 equal parts, sort each part and do a 3 way merge.What would the worst-case complexity of this ver...
0 votes
0 votes
1 answer
4