1
$\begingroup$

I wanted to know which implementation is better to find the root of the element in the Quick Union implementation of the UnionFind problem. The professor has used a while loop to find the root of the element, while I have implemented it using a recursive approach. Which approach is better in terms of space complexity, and scalability for large arrays?

//Quick union method for Union-find algorithm. Lazy approach


import java.util.Scanner;

public class QuickUnionUF {

    private int [] id;
    public QuickUnionUF(int N)
    {
        id= new int[N];
        for(int i=0; i<id.length;++i)
        {
            id[i]=i;
        }
    }

    public int root(int p)
    {
        if(id[p]==p) return p;
        else return(root(id[p]));
    }

    public boolean isConnected(int p, int q)
    {
        return (root(p)==root(q));
    }

    public void union(int p, int q){
        int proot= root(p);
        int qroot= root(q);

        id[proot]= qroot;
    }

}

For the root function, the professor has used -

public int root(int p) {
        while (p != id[p])
            p = id[p];
        return p;
    }

https://algs4.cs.princeton.edu/15uf/

$\endgroup$
1
$\begingroup$

The time complexity for both versions is exactly the same. It is linear in terms of the distance between $p$ and the $root$.

Space complexity is a little different. It's easy to see that the iterative version will use constant space. The recursive function will use linear space on paper (each recursive call must store some information about the current function call, for instance in a call stack via stack pointer).

This might give problems, if the distance between $p$ and $root$ is very long. Image a tree with $id[0] = 0$ and $id[p] = p - 1$ for $p > 0$. Then finding the root for a large element $p$ might exceed the allocated stack and crash the program.

However in practice the situation might look a bit different. Depending on the programming language, the compiler/interpreter, configuration this linear space can be optimized to constant space. The concept that allows such an optimization is called tail recursion. E.g. gcc -O3 will generate exactly the same assembler code for both versions: example. But be careful, not all languages, compiler / interpreter have these optimizations implemented.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.