The Gateway to Computer Science Excellence

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,251 answers

198,061 comments

104,693 users