0

Learning about Kruskal's algorithm and searching for the BigO of this algorithm, I have ended up finding two answer equally dispersed:

For E = Number of edges in the graph. For V = Number of vertices in the graph.

Kruskal's algorithm is know to have either:

O(E log E)
or
O(E log V)

Searching further and going on the English wiki page of the algorithm I've found what seem to be an explanation:

E is at most V^2 and log(V^2) = 2*log(V) = O(log(V))

But I don't get it, why 2*log(V) = O(log(V)) shouldn't it be O(2*log(V))?

avallete
  • 53
  • 8
  • 2
    Big `O` notation ignores constant factors, so `2 N = O(N)`. Here are some references: [Wikipedia](https://en.wikipedia.org/wiki/Big_O_notation), [stackoverflow](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation). – hilberts_drinking_problem Apr 12 '20 at 07:46
  • Wikipedia also says that both versions are equivalent. It just depends on what you like better. – AbcAeffchen Apr 13 '20 at 18:05

0 Answers0