Log In
1 vote

First statement is False because complexity will be O(E2).

I think the second statement is true? But not sure

in Algorithms 209 views

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)


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)


1- it will be O(V + EV) = O(EV), hence false

2- false, due to word 'always disconnected' in case of Kruskal

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).



apply kruskal in this graph you will get only single connected tree at every connected

Thanks @joshi_nitish I got the answer.

Please log in or register to answer this question.

Related questions

0 votes
0 answers
Time Complexity of Kruskal - O(mlogm + n.O(1) + m.logn) mlogm --> for sorting edges in increasing order. n.O(1) --> n UNIONS as we've n nodes in G and each takes O(1) m.logm --> Find operation takes logn time as height of tree can never me more than logn and we have m such find operations as we have m edges in G. Now my doubt is - is it O(mlogm) or O(mlogn)? I know, given is O(mlogn), but how?
asked Apr 11, 2018 in Algorithms iarnav 130 views
1 vote
1 answer
Which algorithm does kruskal uses for detecting every cycle and what is the time complexity?
asked Sep 27, 2017 in Algorithms rahul sharma 5 209 views
1 vote
1 answer
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is decreased by the same value (constraint is - keeping all edge positive all the time), then is it TRUE or FALSE? Shortest path between any pair of vertices does not change?
asked Apr 11, 2018 in Algorithms iarnav 278 views
1 vote
1 answer
Complexity of Kruskal's algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are unsorted is _______ ______________________________________________________________________________ If elements are sorted we do with Union Find algo with inverse of ... $log^{*}V$ Now from here can we derive it for unsorted edges? for ref: here
asked Jun 30, 2018 in Algorithms srestha 454 views