CODEWITHSUNDEEP
ctime-complexitydisjoint-sets
chae yeon
chae yeon

Reputation: 33

Time complexity and height of disjoint sets using array in C

I found a quiz about the time complexity of disjointed sets when using an array.

Suppose we have nodes that are numbered from 0 to n-1. All we need is an array named parent, where the value of parent[i] is the ID of the parent node i. If node i is a root node, parent[i] is -1. Below is an example of disjointed sets and their array representation.

If there are nodes with ten numbers 0,1,2,3,4,5,6,7,8,9 and they are making disjointed sets.

Then the array called parent[i] will be like {-1,4,-1,2,-1,2,0,0,0,4} and there are two basic operations about disjoint sets : Find(i) and Union(i,j)

int simpleFind(int i) {
    for( ; parent[i] >= 0; i = parent[i])
       ;
    return i;
}

void simpleUnion(int i, int j) { /* i and j must be roots */
    parent[i] = j;
}

There are two questions I want some help with!

I think the answer to the first question is n-1 when these nodes are connected as one line. I can not figure out the second question. Is it o(log n)?

Upvotes: 0

Views: 111

Answers (1)

tstanisl
tstanisl

Reputation: 14157

Question 1.

I guess the answer to the first question is n-1 as OP suspects. Imagine a sequence of operations:

simpleUnion(0,1);
simpleUnion(1,2);
...
simpleUnion(n-2,n);

The parent of node 0 would be 1, parent of 1 would be 2 and so on. The tree would degenerate to a list of length n.

Question 2.

Run simpleFind(0) on the tree from Question 1. Loop would iterate over all nodes of the tree. Thus the complexity is O(n).

Upvotes: 1

Related Questions