CODEWITHSUNDEEP
algorithmbig-ograph-theoryminimum-spanning-treekruskals-algorithm
Won Young Jung
Won Young Jung

Reputation: 35

Why can't edges be fewer than vertices in Graph theory?

Upon analyzing Kruskal's Algorithm, Kruskal's Algorithm is apparently considered to be E log E because "for an MST to exist, E can't be smaller than V so assume it dominates"

However, the simplest tree input would have more vertices than edges...

snippet of the lecture slide I was looking at

Can someone tell me why "for an MST to exist, E can't be smaller than V so assume it dominates"

hence run time is ElogE not ElogE + V

Upvotes: 1

Views: 186

Answers (1)

myrtlecat
myrtlecat

Reputation: 2276

The term "smaller" here should be understood in terms of computational complexity, or big-O.

For an MST to exist, E must be greater than or equal to V - 1. While you are right that this means E can be less than V, it puts it in the same complexity class.

For graphs that have an MST, E can be O(V), or O(V^2), or anything in between.

Upvotes: 1

Related Questions