Kruskal Algorithm running time is :
a.O(m log n) (m = edges, n = node b.o(n logm) (m = edges, n = nodes)
C. .O(m log m) (m = edges, n = nodes)
d.O(n log n) (m = edges, n = nodes)

Question

Kruskal Algorithm running time is :
a.O(m log n) (m = edges, n = node b.o(n logm) (m = edges, n = nodes)
C. .O(m log m) (m = edges, n = nodes)
d.O(n log n) (m = edges, n = nodes)

Accepted Answer

⚹ The running time of Kruskal's Algorithm is primarily determined by the time it takes to sort the edges and the time it takes to perform the union-find operations. The sorting of the edges takes $O(m \log m)$ time, where $m$ is the number of edges. The union-find operations can be performed in nearly constant time per operation, which leads to $O(m \alpha(n))$, where $\alpha(n)$ is the inverse Ackermann function, which grows very slowly and is practically considered constant. Therefore, the total running time of Kruskal's Algorithm is dominated by the sorting step, which leads to the correct answer being: ⚹ C. $O(m \log m)$ (m = edges, n = nodes) ⚹⚹

Sia