GATE CSE 1992 | Question: 01,ix

Question

Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing $n$ vertices and $m$ edges if the edges are sorted is _______

Comments

Answer should be: $O(E)$

---

If edges are already sorted then we only need to check cycle.

---

1. Sorting Phase: To sort \(E\) edges by weight takes \(O(E \log E)\) time.
2. Cycle Detection Phase: Iterating through the sorted edges using an optimized Union-Find structure takes \(O(E \cdot \alpha(V))\) time.
   
   where \(\alpha \) is the inverse Ackermann function. \(\alpha(V) \le 4\) for all practical sizes of the universe, it behaves like a constant \(O(1)\).
   
   In a simple connected graph, the number of edges \(E\) can be at most \(V^{2}\) (in a dense complete graph). Mathematically:
   \(\log E\le \log (V^{2})=2\log V\)

\(\text{Total\ Time}=\underbrace{O(E\log E)}_{\text{Sorting\ (Dominant)}}+\underbrace{O(E\cdot \alpha (V))}_{\text{Cycle\ Detection}}=\mathbf{O(E}\log \mathbf{E)}\)

Answer 1

IF EDGES ARE ALREADY SORTED, THEN IN WORST CASE WE HAVE TO TRAVERSE THE WHOLE EDGES TO GET MINIMUM SPANNING TREE. M EDGES WILL BE TRAVERSED AND WE HAVE TO DO UNION OPERATION WHICH TAKE O(LOGN) TIME, SO COMPLEXITY WILL BE Mlog(n).

Answer 2

Since the edges are sorted, we simply need to visit the vertex, and select an edge.

Now, Selecting an edge means, check if the edge creates a cycle or not and if not then insert. It does not consume a lot of time, we can assume it to be an O(1) operation.

So we need to visit all the vertices: O(n)

And we need to perform Select operation for m edges: O(m) (worst case).

So overall time complexity is O(m+n).

Answer 3

O(n log n)

 

Answer 4

Detailed Analysis
 

Time Complexity analysis of Kruskal = Time to sort the edges in inreasing order (A) + time to detect cycle for every edges (B)

Since, the edges are already sorted (given in question). Hence, A = 0

Let, number of edges = E and, number of vertices = V

Now for B, B = E (no. of edges) * time to detect cycle

Time Complexity of detecting cycle

Using Union-Find : O(1) i.e, contant time
Using DFS/BFS = O(V+E)

Since, in question, which algorithm is used to detect cycle is not given, we will consider Union-Find Algorithm
Therefore, Time Complexity analysis of Kruskal = A + B = 0 + E*(O(1)) = O(E) = O(m) ------ (Final Answer)

Extended Analysis

If BFS/DFS is used for cycle detection,
Time Complexity analysis of Kruskal = A + B = 0 + E*(V+E) = VE + V^2

Case 1: If the  graph is densed, then E = V^2 (approx)

Case 2: If the graph is sparsed, then E = V (approx)

Therefore, for Case 1: Time Complexity of Kruskal = VE + V^2 = V*(V^2) + (V^2)^2 = O(V^4) = O(n^4)
And, for Case 2: Time Complexity of Kruskal = VE + V^2 = V*(V) + V^2 = O(V^2) = O(n^2)

Answer 5

O(m α(n))​ — using Union–Find with union by rank + path compression (since sorting is already done).
(In practice α(n) is tiny, so it’s ~O(m). With a naïve DSU it would be O(m log⁡ n))

Let's understand easy way

Kruskal’s Algorithm Steps

1. Sort all edges by weight.

2. Take edges one by one (from smallest to largest).

3. Use Union–Find (Disjoint Set Union, DSU) to check if adding the edge makes a cycle.

   • If not, include it in the MST.

   • If yes, skip it.

Now complexity:

• Sorting edges → Normally O(mlog⁡m).
  But in the question it says edges are already sorted, so this part is skipped.

• Union–Find operations → For each of the mmm edges, we do at most 2 finds + 1 union.
  With efficient DSU (path compression + union by rank),
  each operation is almost constant: O(α(n)),
  where α(n) = inverse Ackermann function (grows super slowly, < 5 for all practical inputs).

So total = O(m⋅α(n))

which is basically linear in number of edges.

Final Answer:
If edges are already sorted, Kruskal’s algorithm runs in O(m α(n)) time.
(Without sorting, it would be O(mlog⁡m).)

 

Answer 6

ANSWER SHOULD BE O(V+E).

Comments

Answer will be O(E LogV)  because we have to check for all the edges if there is any cycle while including in MST.

Some have given answer O(E+V) which is wrong.