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.