# Cormen Edition 3 Exercise 23.2 Question 6 (Page No. 637)

715 views
Suppose that edge weights are uniformly distributed over half open interval $[0,1)$. Which algorithm kruskal's or prim's can make you run faster?

edited

In this scenario kruskal's algorithm will run faster than prim's. The time complexity of kruskal's algorithm is

O(E log E) <--(time taken to sort E edges)      +    (E α(V)) <--  find set and union operations

Given that edge weights are uniformly distributed over half open interval [0,1), we can sort the edge list in O(E) time using bucket sort (see CLRS Bucket sort).

So now the running time of kruskal's MST algorithm will become

O(E) + (E α(V))

where α(V) is the inverse ackermann function whose value is less than 5 for any practical input size 'n'. (ref wiki)

so, the running time of kruskal's MST algorithm is linear, where prim's will still work in O((V+E)log V)

selected

## Related questions

1
778 views
Can Prim's and Kruskal's algorithm yield different minimum spanning trees? Explain why or why not.
Consider the problem of adding two $n$-bit binary integers, stored in two $n$-element arrays $A$ and $B$.The sum of the two integers should be stored in binary form in an $(n+1)$-element array $C$. State the problem formally and write pseudocode for adding the two integers.