GATE CS 1991 Q03 — Minimum Spanning Trees

The standard time complexity of Kruskal’s algorithm for a graph with $n$ vertices and $m$ edges is dominated by the step of sorting the edges:

• Sorting $m$ edges takes $O(m \log m)$ time.
• Since $m \le n^2$, we have $\log m \le 2 \log n$, which means $O(m \log m) = O(m \log n)$.
• The disjoint-set operations (using union by rank and path compression) take $O(m \alpha(n))$ time, which is strictly dominated by the sorting step.

Thus, the tightest upper bound for Kruskal's algorithm is $O(m \log n)$ (Option D).

By the definition of Big-O notation ($f(x) = O(g(x))$ represents an asymptotic upper bound):

1. Option D ($O(m \log n)$): This is the standard tight upper bound.
2. Option B ($O(mn)$): Since $\log n \le n$ for all $n \ge 1$, we have $m \log n = O(mn)$. Therefore, $O(mn)$ is also a valid upper bound.
3. Option E ($O(m^2)$): For any connected graph, $m \ge n - 1$, which implies $\log n = O(m)$. Thus, $m \log n = O(m^2)$, making $O(m^2)$ a valid upper bound as well.

Hence, options B, D, and E are all mathematically correct upper bounds.