How to understand the complexity of Kruskal implemented with Quick-Union by rank and path compression?

Question

I'm trying to understand the complexity of the Kruskal algorithm implemented with the Quick-Union by rank and with the path compression.

Now there is a theorem for the last structure above:

The complexity of any sequence of m operations of Makeset, Union and Find, n of which are of Makeset, on a Quick Union by rank and path compression is in the worst case equal to $O(m\,\, G(n))$. Where $G(n)$ is the inverse of the Ackerman function

And this one is the Kruskal algorithm in pseudocode. Let $G=(V,E)$ be an undirected, connected and weighted graph, where $V$ is the set of vertices and $E$ the set of edges, then the following algorithm returns a Set $A$ that contains the edges of the Minimum Spanning Tree.

Kruskal(Graph G) {
    Set A                          

    For every vertex v in V {
         Makeset(v)
    }

    Order the edges in E in ascending order by weight

    For every edge (u,v) {
        If find(u) != find(v) {
            union(u,v)
            A = A + (u,v)
        }
    }

    Return A
}

Let's go back to my problem.
I understand that the second loop is executed at the worst $m$ times (the number of edges). Hence the number of operations of union and find is $m$, while the number of makeset is $n$ (the number of vertices).

The book where I'm studying, after making similar observations says that the complexity of the above operations equals to $O((m+n)\,\,G(n))$ and I don't get why. Of course, the other complexity to order the edges is $O(m\,\, log\, m)$ so the final one is:
$O(m\,\, log\, m) + O((m+n)\,\,G(n))$
But $m>n-1$ then
$=O(m\,\, log\, m) + O((m)\,\,G(n))$
However $m<n^2 \implies log\, m < 2log\, n \implies log(m)=O(log n)$, so
$=O(m\,\, log\, n) + O((m)\,\,G(n))$
$=O(m\,\, log\, n)$

Can you explain to me how to get the $O((m+n)\,\,G(n))$ complexity from the algorithm?

Answer 1

You are absolutely right. There is nothing wrong with your reasoning.

The running time of Kruskal's algorithm, when implemented in the way you describe, is $O(m \log m)$, or equivalently, $O(m \log n)$. If the book says its running time is $O((m+n) G(n))$, the book is wrong; that doesn't take into account the time to sort the edges by weight.

If you look at other sources I think you'll find that they correctly report the running time of Kruskal's algorithm.

Answer 2

You get the inverse Ackerman function when you look deeper into the complexity of the find operation. I recommend trying to understand the simpler $O(log^*n)$ explanation (which is available here) before trying to understand the inverse Ackerman function one.