1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.