2 votes

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?

4 votes

Best answer

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)**