Search code examples
algorithmbig-okruskals-algorithm

why E dominates v?

I analyzed the running time for Kruskal algorithm and I come up with O(ElogE+Elogv+v)

I asked my prof and he said that if the graph is very sparse with many isolated vertices V dominates E which makes sense if not then E dominates V and I can not understand why? I can give an example where graph is not sparse but still V is greater than E

Can anyone help me to clear this confusion?

Solution

  • A tree in a undirectional graph has |V|-1 edges.

    Since a tree is the connected component with least edges as possible - it basically means that for each connected undirectional graph, |E| is in Omega(|V|), so |V| is dominated by |E|.

    This basically means that if |E| < |V|-1 - the graph is not connected.

    Now, since Kruskal algorithm is designed to find a spanning tree, you can abort the algorithm once you have found |E| < |V|-1 - there is no spanning tree at all, no point to look for one.

    From this we conclude that when |E| < |V|-1, there is no point in discussing complexity of Kruskal Algorithm, and we can safely assume that |E| >= |V| -1 , so |V| is dominated by |E|.