# 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 < 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 < 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.