R72 Suppose a social network N contains n people m edges and

R-7.2: Suppose a social network, N, contains n people, m edges, and c connected components. What is the exact number of times that each of the methods, makeSet,union, and find, are called in computing the connected components for N using the following algorithm:

Algorithm UFConnectedComponents(S, E): Input: A set, S, of n people and a set, E, of m pairs of people from S defining pairwise relationships outyut: An identification, for each r in S, of the connected component con taining r for each r in S do make Set (r) for each (r,y) in Edo if find(r) find(y) then union (find(r), find(y)) for each r in S do output \"Person z belongs to connected component\" find(r) Algorithm 7.2: A connected components algorithm using union and find.

Solution

Solution:

1) From the above algorithm:

for each x in S do

makeSet(x)

for loop run for N times since there are N elements in Set S.

for each element in set S makeSet method executes.

Therefore, makeset() method execute N times in algorithm O(N) times..

2) for each(x,y) in E do

if(find(x)!=find(y)) then ---------equation 1

union(find(x),find(y)) ----------equation 2

for each x in S do

output \"person x belongs to connected component\" find(x)----------- equation 3

Solution :

FIND METHOD:

In above lines Set E contains pairs of elements of S therefore it contains N/2 elements.

In equation 1 : for each pair find method executes 2 times i.e.find(x) and find(y) .

since there are N/2 pairs,

total no of executions in equation 1 = N/2*2=N times= O(N) times

In Equation 3: printing find(x) in Set S consists of N elements takes N imes executions.

Therefore , total find() method executions = N*N+N = N^2+N=O(n^2) times

UNION METHOD:

In Equation 2: No of Sets in E =N/2;

Union (find(x),find(y))

   so union function executes for each element in Set E which contains N/2 elements.

   Therefore, Union() method executes N/2 times O(N/2).