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 objectsHow 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 accessesWhat 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.
Problems understanding the Union functionality of the Union-Find Algorithm
algorithms;asymptotics;union find
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.