About the time complexity

#1

pls someone explain me the time complexity of prim’s and kruskal’s algorithms

#2

hello @Senjuti256
time complexity of prims (using adjacency list)->
Let’s consider a graph in which there are V vertices numbered
from 0 to V-1 and E number of edges in the form (i,j). Where (i,j)
represent an edge from i
th vertex to j
th vertex.
Sorting a graph as an adjacency list has a space complexity of
O(|V|+|E|), that is the sum of vertices and edges. Because in an
adjacency list for every vertex there is a linked list which have the
values of the edges to which it is connected.
The inner loop has the operation to find the minimum value node
which takes O (log V) time.
So, the overall time complexity is O(V+E) *O (log V),
Which is O((V+E) *log V) = O (E log V)

time complexity of kruskals->
let E be the edge , V be the verticies.

sorting time will be -> ELog(E)
now we need to pick E-1 edges with no cycle , for checking cycle we are using union find datastruture which take Log(v) per operation.
so time used in this will be E log(V)

so total time will -> Elog(E) + E log(V) -> E( log(e) + log(v) )

and becuase v > e we ignore log(e)
so
time complexity will be
E(log(v))

#3

In prims why is that O(E+V) coming pls can you explain to me pls

#4

E+V is the size of graph in case of adjacency matrix.
in worst case we will we traversing whole graph which is E+V and to find minimum each time is logv
hence time complexity is (E+V) * log(V)

#5

For an undirected graph won’t the space reqd be 2e+v?

#6

here E stands for total no of edges.

#7

Yes but for a bidirectional graph each edge represents 2 pathways right? Can you pls explain me then why the space complexity be O(v+e)?

#8

we are storing each vertices and their neigbours (which is same as number of edges they are connected with) in adjacency list.
thats why v + e (all vertices + all edges)

#9

What is the time complexity to sort an adjacency list of weighted graph? How is it so?

#10

we cant sort adj list.

if we want edges in sorted order then we will use edge list.

#11

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.