Problems understanding the Union functionality of the Union-Find Algorithm I am currently doing a course based on algorithms (Coursera). I've come across an algorithm called quick find. The course does have reference to Big O Notation. Despite the fact that I do not have much knowledge of Big O, I have been doing some basic reading.



Implementation (Java):

Initializes the array:

public QuickFindUF(int N)
{
    id = new int[N];
    for (int i = 0; i &lt; N; i++)
    id[i] = i;
}


Checks if two input values are connected:

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


Union Implementation:

public void union(int p, int q)
{
    int pid = id[p];
    int qid = id[q];
    for (int i = 0; i &lt; id.length; i++)
    {
        if (id[i] == pid)
        {
            id[i] = qid;
        }
    }
}


The id variable is a private instance variable.



My Problem:

1) In the study material it says:


  It takes N2 array accesses to process a sequence of N union
  commands on N objects


How can it take N2 if the union method only has a single for loop?

2) It also says that the union method takes 


  at most 2N + 2 array accesses


What does this mean? My speculation is that 2N could mean that the array is accessed twice (line 7 and line 9 of the union method). I have no idea what + 2 refers to though.



I apologize if I have incorrectly stated something.

Any help would be highly appreciated. Thank You.
The answer to your first question is that while it takes (roughly) $N$ array accesses to perform one union operation, it takes (roughly) $N^2$ to perform $N$ of them. This is what is meant by the phrase "a sequence of $N$ union commands".

Regarding your second question, the first two operations are those that initialize pid and qid, and the body of the loop (which runs up to $N$ times) contains two more, one which compares an entry to pid, and another which assigns qid to the same entry.