kaamchor
September 25th, 2009, 09:33 PM
Consider the following code segment:
for i = 1 to n
makeset(i)
for i = 1 to n − 1
union(find(i), find(i + 1))
for i = 1 to n
find(i)
For each of the following cases, analyze the time complexity of the above
sequence:
(a) when no weighted union and no path compression heuristic is used.
(assuming union(p,q) always makes p a child of q.)
(b) when only weighted union heuristic is used.
(c) when both weighted union and path compression heuristic are used.
for i = 1 to n
makeset(i)
for i = 1 to n − 1
union(find(i), find(i + 1))
for i = 1 to n
find(i)
For each of the following cases, analyze the time complexity of the above
sequence:
(a) when no weighted union and no path compression heuristic is used.
(assuming union(p,q) always makes p a child of q.)
(b) when only weighted union heuristic is used.
(c) when both weighted union and path compression heuristic are used.