Complexity of Kruskal's algorithm - Theory

This is a discussion on Complexity of Kruskal's algorithm - Theory ; I came across this question which asked: Complexity of Kruskal's algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are sorted is a) O(mn) c) O(m) b) O(m+n) d) ...

+ Reply to Thread
Results 1 to 2 of 2

Complexity of Kruskal's algorithm

  1. Default Complexity of Kruskal's algorithm

    I came across this question which asked:

    Complexity of Kruskal's algorithm for finding the minimum spanning
    tree of an undirected graph containing n vertices and m edges if the
    edges are sorted is


    a) O(mn) c) O(m)
    b) O(m+n) d) O(n)

    Answer: O(m+n)

    This is how I understood it. Derived the reasoning from the Answer key
    (which did not explain properly) and just indicated t
    hat it grows linearly over the edges so, O(m) can also be correct.

    Actually the kruskal algorithm for minimum spanning tree with m edges
    n vertices O(n) + O(m logm).

    But this is already sorted, so its order so log m comparisions is not
    required and it is just over the edges.
    So, O(n) + O(m) = O(m+n)

    Is my understanding correct or, we can assume that the complexity is
    just over the edges and so it is O(m).

    Thanks,
    Senthil

  2. Default Re: Complexity of Kruskal's algorithm

    The correct answer is O(m log n). Even if the edges are sorted, each
    step requires you to do a union/find operation, which for simple union/
    find data structures takes O(log n) time. There isn't one that can do
    it in constant time, although you can get close.

    So none of the answers is correct.

    On Oct 17, 4:58 am, "O.R.Senthil Kumaran" <orsent...@gmail.com> wrote:
    > I came across this question which asked:
    >
    > Complexity of Kruskal's algorithm for finding the minimum spanning
    > tree of an undirected graph containing n vertices and m edges if the
    > edges are sorted is
    >
    > a) O(mn)    c) O(m)
    > b) O(m+n)   d) O(n)
    >
    > Answer: O(m+n)
    >
    > This is how I understood it. Derived the reasoning from the Answer key
    > (which did not explain properly) and just indicated t
    > hat it grows linearly over the edges so, O(m) can also be correct.
    >
    > Actually the kruskal algorithm for minimum spanning tree with m edges
    > n vertices O(n) + O(m logm).
    >
    > But this is already sorted, so its order so log m comparisions is not
    > required and it is just over the edges.
    > So, O(n) + O(m) = O(m+n)
    >
    > Is my understanding correct or, we can assume that the complexity is
    > just over the edges and so it is O(m).
    >
    > Thanks,
    > Senthil



+ Reply to Thread