Time complexity of quick find

[adam2016]

Hi guys

so I am following a pdf on princetons coursera algorithms course, it basically tells me the quick find algorithm ( I'm guessing the unionNodes function ) is quadratic time,

I fail to see how this function is quadratic time, I do understand that he is talking about potentially worse case? ... right?

lets say we have 10 nodes [0,1,2....9], that also means that we must have 10 connection points ( maximum ) so I'm guessing this why this function is N^2 right?

I probably already answered my own question after breaking it down, but I just want to confirm if this thinking is right?

obviously we could just connect 4 nodes and this clearly wouldn't be N^2 but we are talking about worst case in most situations when it comes to time complexity right?

   // this technically wouldn't be N^2 because it is not worse case right?

    UF un(10);
    un.unionNodes(0,1);
    un.unionNodes(2,3);
    un.unionNodes(3,8);
    un.unionNodes(7,8);
    un.unionNodes(1,2);

    
    // so we have 10(N) nodes and we connect ten 10(N) nodes 
    // therefore we loop 10 times * 10 times ( because we have 10 
    // connection points so this 10*10 = 10^2 = N^2
    // is this why this algorithm is considered N^2???

    UF un(10);
    un.unionNodes(0,1);
    un.unionNodes(1,2);
    un.unionNodes(2,3);
    un.unionNodes(3,4);
    un.unionNodes(5,6);
    un.unionNodes(6,7);
    un.unionNodes(7,8);
    un.unionNodes(8,9);
    un.unionNodes(4,9);
    un.unionNodes(0,5);

   un.unionNodes(1,6); // this will be ignored as 1 and 6 are already connected
                                 // so technically we can't go past N*N 

Thanks!

extra reading and extra information on the question -
(exact same algorithm in question ) https://stackoverflow.com/questions/24243747/how-is-union-find-quadratic-algorithm

  #include <iostream>

using namespace std;

class UF{

public:
    int size;
    int* id;

    UF(int size): size(size){

        id = new int[size];

        // init each node to put to themselfs as parent
        for(int i = 0; i < size; ++i)
            id[i] = i;
    }

    bool connected(int a,int b){

      if(a > size || a < 0)
        return false;
      if(b > size || b < 0)
        return false;

      return (id[a] == id[b]);
    }

    void unionNodes(int a,int b){

      if(a > size || a < 0)
        return;
      if(b > size || b < 0)
        return;

       int aID = id[a];
       int bID = id[b];

       for(int i = 0; i < size; ++i){

          if(id[i] == aID)
            id[i] = bID;
       }
    }
};

int main()
{
    UF un(10);
    un.unionNodes(0,1);
    un.unionNodes(2,3);
    un.unionNodes(3,8);
    un.unionNodes(7,8);
    un.unionNodes(1,2);

    un.unionNodes(5,6);

    if(un.connected(1,6))
        cout << "connected" << endl;
    else
        cout << "nodes not connected" << endl;
}

[helios]

The link you posted says

The instructor said that union is too expensive as it takes N^2 to process sequence of N union commands on N objects

This is correct. If a UF instance is initialized with size n and UF::unionNodes() is called n times, the time complexity will be quadratic.
UF::unionNodes() itself, however, takes linear time.

I don't know what the "quick find" algorithm is, but the slowest search algorithm (save for joke algorithms) on a sequence takes linear time.

[dutch]

The maximum number of connections in a graph with N elements is (N * (N - 1)) / 2, which is O(N^2).

[adam2016]

so UF::unionNodes() is technically O(N)? but in the worse case scenario is it O(N^2) (if we call it N times with N > 1) right?

The maximum number of connections in a graph with N elements is (N * (N - 1)) / 2, which is O(N^2).

never seen this formula, but this is the max number of connections we can have for N nodes? in this examples case it only allows for N connections though.

[helios]

so UF::unionNodes() is technically O(N)? but in the worse case scenario is it O(N^2) (if we call it N times with N > 1) right?

The cost of running m times an O(f(n)) operation is O(m*f(n)), so if you run UF::unionNodes() n times, it will cost O(n^2).

never seen this formula, but this is the max number of connections we can have for N nodes? in this examples case it only allows for N connections though.

dutch is talking about a general undirected graph. Yours is not a general graph because each node is only allowed to point to one other node.

[dutch]

never seen this formula

It's the well-known formula for adding numbers from 1 to N (discovered by Gauss (or Pascal?) as a child, IIRC).

1 + 2 + 3 + ... + N == (N * (N+1)) / 2

You can easily see this is true with an example, the sum of 1 to 10:

 1 +  2 +  3 +  4 +  5 +  6 +  7 +  8 +  9 + 10
10 +  9 +  8 +  7 +  6 +  5 +  4 +  3 +  2 +  1
===============================================
11 + 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11 = 10 * 11

And since that's twice the value we want, we divide it by 2.

In a graph, node 1 can connect to 2, 3, ..., N, which is N-1 connections.
Node 2 can connect to 3, 4, ..., N (it's connection to 1 is already accounted for), which is N-2 connections.

So we need to add 1 to N-1, which is ((N-1) * N) / 2.

[adam2016]

Thanks guys, makes sense

Graph theory is interesting, unfortunately I never gave it much attention in college,

in our math class we had 4 main topics

Graph Theory
Calculus
Matrices
Statistics & probability

we only had to choose 3/4 , I choose the latter 3. I kind of wish I would have paid more attention to it as it seems to probably or arguably have the most applications in programming.

[helios]

That's a tough choice. For CS calculus and probability are the least useful, IME, but they occasionally come in handy. Graph theory and matrices (and linear algebra in general) are a must.