Re: Doubt on kruskal algog's complexity

On May 26, 2:13 pm, "prakash.saiva...@xxxxxxxxx"
<prakash.saiva...@xxxxxxxxx> wrote:
Hi all,
The following is snippet of famous kruskals algorithm

e = deletemin (edges);

let e = (u, v);

ucomp = find(u, components);

vcomp = find(v, components);

if (ucomp! = vcomp)

{

merge (ucomp, vcomp, components);

ncomp = ncomp - 1;

}

Aho Ullman states that the complexity of MERGE and FIND is O(e log e)
is it not O(e log n) since we are operating the MERGE anf FIND on
vertices only ( assuming n vertices ).

Thanking you
Prakash S

They're really the same thing. e <= n^2, so log e <= 2 log n , but a
constant factor of 2 doesn't change asymptotic complexity.

The more important thing is that you can do better than log with
collapsing finds.

.

Relevant Pages