Time Complexity: Minimum spanning tree (Kruskal's)
O(E log E)
0
0
Minimum spanning tree (Kruskal's) in Data Structures Theory - Time & Space Complexity
Understanding Time Complexity
Analyzing the time complexity of Kruskal's algorithm helps us understand how its running time grows as the graph size increases.
We want to know how the number of edges and vertices affects the work needed to find the minimum spanning tree.
Scenario Under Consideration
Analyze the time complexity of the following Kruskal's algorithm snippet.
function kruskal(graph):
mst = empty set
sort edges by weight ascending
for each edge in sorted edges:
if adding edge does not form cycle:
add edge to mst
return mst
This code finds a minimum spanning tree by sorting edges and adding them if they don't create cycles.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Sorting all edges by weight.
- How many times: Sorting runs once on all edges; then each edge is checked once for cycle formation using union-find operations.
How Execution Grows With Input
As the number of edges and vertices grow, sorting edges takes more time, and checking cycles grows with edges.
| Input Size (n = edges) | Approx. Operations |
|---|---|
| 10 edges | About 10 log 10 + 10 union-find checks |
| 100 edges | About 100 log 100 + 100 union-find checks |
| 1000 edges | About 1000 log 1000 + 1000 union-find checks |
Pattern observation: The sorting step dominates and grows a bit faster than linearly as edges increase.
Final Time Complexity
Time Complexity: O(E log E)
This means the time grows roughly proportional to the number of edges times the logarithm of that number.
Common Mistake
[X] Wrong: "Since we only add edges one by one, the algorithm runs in linear time O(E)."
[OK] Correct: Sorting edges takes more than linear time, and cycle checks add extra work, so the total time is more than just going through edges once.
Interview Connect
Understanding Kruskal's time complexity shows you can analyze how sorting and data structure choices affect algorithm speed, a key skill in many coding challenges.
Self-Check
"What if we used a different data structure for cycle detection, like a simple visited array instead of union-find? How would the time complexity change?"