search
Log In
3 votes
1.5k views

Explain 

  • Prims Algorithm
  • Analysis Of Time Complexity
  • How does $\mathcal{O}(VlogV + ElogV)=\mathcal{O}(ElogV)$
in Algorithms
retagged by
1.5k views

1 Answer

0 votes
The no. of edges in a sparse graph can be $(V-1)$ and in dense, it may go up to $O(V^2)$

therefore it wouldn't be incorrect to write$ O(ElogV +VlogV)= O(ElogV)$

edited by
4
if connected :)
0
Oh yes

Related questions

2 votes
0 answers
1
568 views
I have seen many varients of complexities using diferent data structures in implementing Prims Agorithm. Can you pls post standard algorithm and tells me in details how to derive the complexities. Please also mention the variations possibles when data structure changes and How will effect the complexity taking Best case and Worst case senarios .
asked Dec 18, 2016 in Algorithms PEKKA 568 views
2 votes
3 answers
2
780 views
Consider the following graph and Assume node ‘P’ as the starting vertex for Prim’s algorithm. Which of the following can be the correct order of edges in which they are added to construct Minimum Spanning Tree (MST)? P-Q, P-X, X-V, V-U, U-R, R-S, R-W, S-T P-Q, P-X, X-V, V-U, U-R, R-W, R-S, S-T P-Q, Q-R, R-W, W-V, V-X, V-U, R-S, S-T P-Q, Q-R, R-W, R-S, V-X, V-U, W-V, S-T
asked Nov 17, 2017 in Algorithms Parshu gate 780 views
1 vote
0 answers
3
299 views
Assuming that the graph can contain repeated edge weights, we have a single tree at any instance when applying Prim's algorithm. Justify this statement.
asked Oct 30, 2017 in Algorithms just_bhavana 299 views
3 votes
2 answers
4
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
...