
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

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