search
Log In
2 votes
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?
in Algorithms
edited by
715 views

1 Answer

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)


selected by

Related questions

2 votes
3 answers
1
778 views
Can Prim's and Kruskal's algorithm yield different minimum spanning trees? Explain why or why not.
asked Oct 26, 2016 in Algorithms Geet 778 views
5 votes
1 answer
2
705 views
Given graph using Prim’s or Kruskal’s algorithm, find out that how many distinct minimum cost spanning trees are possible___? My answer was 1 and given is 2 ,what I am missing ? Edit:I had confirmed with it and answer is only one tree possible.
asked Jan 2, 2018 in Algorithms sunil sarode 705 views
3 votes
2 answers
3
2.1k views
It may be the case that "Kruskal's Algorithm may not maintain connectivity while Prim's algorithm always does that" ? Any example which favours this ?
asked Jan 24, 2017 in Algorithms Kapil 2.1k views
0 votes
1 answer
4
53 views
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.
asked Jun 25, 2019 in Algorithms akash.dinkar12 53 views
...