How is union find quadratic algorithm?

Question

In this implementation of Quick Find algorithm, Constructor takes N steps so does union().

The instructor said that union is too expensive as it takes N^2 to process sequence of N union commands on N objects, How can union be quadratic when it accesses array elements one at a time?

public class QuickFind
{
    private int[] id;

    public QuickFind(int N) {
        id = new int[N];
        for (int i=0; i<N; i++) {
            id[i] = i;
        }
    }

    public boolean connected(int p, int q) {
        return id[p] == id[q];
    }

    public void union(int p, int q) {
        int pid = id[p];
        int qid = id[q];

        for (int i=0; i<id.length; i++)
            if (id[i] == pid)
                id[i] = qid;
    }
}

Answer 1

Each invocation of union method requires you iterate over the id array, which takes O(n) time. If you invoke union method n times, then the time required is n*O(n) = O(n^2).

You can improve time complexity of union method to O(1), by making the time complexity of connected method higher, probably O(log n), but this is just one time operation. I believe that your text book explain this in details.