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

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top