CODEWITHSUNDEEP
algorithmquick-union
user3457614
user3457614

Reputation: 61

What is the Time Complexity of Quick Union?

I'm taking the coursera course on Data Structures and Algorithms. The author mentions that Quick Find is O(N^2) which makes sense (given that N union operations on N objects might require N*N array accesses). However, I don't understand why Quick Union would be any better. It seems that in the worst case, one long narrow tree, N Find operations on N objects would also lead to O(N^2) yet the material says it's O(N).

So, one is quadratic time, and one is linear. I'm not sure that I understand why there is a difference. Example:

Quick find approach

int[] id = new int[10];

for(int i = 0; i < 10; i++)
    id[i] = i;  

// Quick find approach

int QuickFind(int p)
{
    return id[p];
}

public void Union(int p, int q)
{
    int pId = find(p);
    int qId = find(q);

    if (pId == qId)
        return;

    for (int i = 0; i < id.length; i++)
    {
        if(id[i] == pId)
            id[i] = qId;
    }
}

Quick union approach

int Find(int p)
{
    while(p != id[p])
        p = id[p];

    return p;
}

void QuickUnion(int p, int q)
{
    int pRoot = Find(p);
    int qRoot = Find(q);

    if(pRoot == qRoot)
        return;

    id[pRoot] = qRoot;
}

Upvotes: 5

Views: 8719

Answers (3)

Azadeh Izadi
Azadeh Izadi

Reputation: 1

I think Quick-find does N union operations on N objects to find 1, but Quick-Union does N find operations on N objects to union N thus, the second is faster

Upvotes: 0

strizzwald
strizzwald

Reputation: 643

I came across this as well. You are right, N find operations on N objects would also lead to O(N^2) for Quick-union. The main difference however is that with Quick-find, when performing a union operation you will always have to iterate through all the objects, this is true for the worst case and best case.

Whereas with Quick-union there there is no need to iterate through all objects, the union of two objects can be done in constant time.

Both approaches will have O(N^2) worst case. Quick-union might slightly be faster in certain scenarios depending on the nature of the input.

This is because with Quick-find, the union operation will always have a computational complexity greater than or equal to N. This is not the case for Quick-union, the find operation can perform computations less than N.

Upvotes: 5

Kaidul
Kaidul

Reputation: 15895

// Naive implementation of find
int find(int parent[], int i)
{
    if (parent[i] == -1)
        return i;
    return find(parent, parent[i]);
}

// Naive implementation of union()
void Union(int parent[], int x, int y)
{
    int xset = find(parent, x);
    int yset = find(parent, y);
    parent[xset] = yset;
}

The above union() and find() are naive and the worst case time complexity is linear. The trees created to represent subsets can be skewed and can become like a linked list. Following is an example worst case scenario.

Let there be 4 elements 0, 1, 2, 3

Initially all elements are single element subsets.
0 1 2 3 

Do Union(0, 1)
   1   2   3  
  /
 0

Do Union(1, 2)
     2   3   
    /
   1
 /
0

Do Union(2, 3)
         3    
        /
      2
     /
   1
 /
0

The above operations can be optimized to O(Log n) in worst case. The idea is to always attach smaller depth tree under the root of the deeper tree. This technique is called union by rank. The term rank is preferred instead of height because if path compression technique (I've discussed it below) is used, then rank is not always equal to height.

Let us see the above example with union by rank
Initially all elements are single element subsets.
0 1 2 3 

Do Union(0, 1)
   1   2   3  
  /
 0

Do Union(1, 2)
   1    3
 /  \
0    2

Do Union(2, 3)
    1    
 /  |  \
0   2   3

The second optimization to naive method is Path Compression. The idea is to flatten the tree when find() is called. When find() is called for an element x, root of the tree is returned. The find() operation traverses up from x to find root. The idea of path compression is to make the found root as parent of x so that we don’t have to traverse all intermediate nodes again. If x is root of a subtree, then path (to root) from all nodes under x also compresses.

Let the subset {0, 1, .. 9} be represented as below and find() is called
for element 3.
              9
         /    |    \  
        4     5      6
     /     \        /  \
    0        3     7    8
            /  \
           1    2  

When find() is called for 3, we traverse up and find 9 as representative
of this subset. With path compression, we also make 3 as child of 9 so 
that when find() is called next time for 1, 2 or 3, the path to root is 
reduced.

               9
         /    /  \    \
        4    5    6     3 
     /           /  \   /  \
    0           7    8  1   2

The two techniques complement each other. The time complexity of each operations becomes even smaller than O(logn) ~ O(n). In fact, amortized time complexity effectively becomes small constant.

I didn't post the code with above optimization because it's the assignment part I guess. Hope it helps!

Upvotes: 5

Related Questions