1 votes 1 votes First statement is False because complexity will be O(E2). I think the second statement is true? But not sure Algorithms algorithms minimum-spanning-tree time-complexity prims-algorithm + – Shivam Chauhan asked Nov 2, 2017 Shivam Chauhan 712 views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Hemant Parihar commented Nov 2, 2017 reply Follow Share I think both are false. For 1st, It will be O(EV) because the decrease-key operation will take O(n) times and we have to perform that operation E times. For 2nd, Kruskal's algorithm is always disconnected. Here always word makes it false, we can intentionally create such a graph where kruskal's MST is also connected. For example: 1 ---> 2 ---> 3 ---> 4 (1) (2) (3) 2 votes 2 votes Shivam Chauhan commented Nov 2, 2017 reply Follow Share First Statement: Sorted linked list wil be the list of edges. so to decrease key operation will take O(E). Time Complexity of Dijkstra = O(V Textract-min + E Tdecrease-key) = O(V + E2). Extract-min takes O(1) 0 votes 0 votes joshi_nitish commented Nov 2, 2017 reply Follow Share for, 1- it will be O(V + EV) = O(EV), hence false 2- false, due to word 'always disconnected' in case of Kruskal 0 votes 0 votes Shivam Chauhan commented Nov 2, 2017 reply Follow Share Second statement is true Because For Prim at each step we have connected tree. For Kruskal at each step we have disconnected tree. Code from Cormen We make separate sets for each vertex and add edges one by one to connect different trees. (always we have a forest). 0 votes 0 votes joshi_nitish commented Nov 2, 2017 reply Follow Share @Shivam, apply kruskal in this graph you will get only single connected tree at every connected 2 votes 2 votes Shivam Chauhan commented Nov 2, 2017 reply Follow Share Thanks @joshi_nitish I got the answer. 0 votes 0 votes Please log in or register to add a comment.