The Gateway to Computer Science Excellence
+1 vote

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

I think the second statement is true? But not sure

in Algorithms by Loyal (8.9k points) | 150 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

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,737 questions
57,258 answers
104,735 users