Problems understanding the Union functionality of the Union-Find Algorithm
-
04-11-2019 - |
Question
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.
No correct solution