Multiple choice

The time required by Kruskal's algorithm is _____.

  1. O(|E|log|V|)

  2. O(VlogE)

  3. O(EV)

  4. O(log V)
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

Kruskal's algorithm uses edge sorting and union-find. Sorting |E| edges takes O(|E| log |E|) ≈ O(|E| log |V|) since |E| ≤ |V|². Union-find operations are nearly O(1) with path compression and union by rank. The dominant cost is sorting, giving O(|E| log |V|). Adjacency list representation is standard.

Keep practicing — related questions