The Gateway to Computer Science Excellence
+2 votes
535 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 by Boss (31.4k points)
edited by | 535 views

1 Answer

+3 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)

by (399 points)
selected by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,251 answers
198,061 comments
104,693 users