Question

Computer Science

Posted 3 months ago

```
Kruskal Algorithm running time is :
a.O(m log n) (m = edges, n = node b.o(n logm) (m = edges, n = nodes)
C. .O(m log m) (m = edges, n = nodes)
d.O(n log n) (m = edges, n = nodes)
```

Sign in to unlock the answer

Answer from Sia

Posted 3 months ago

The running time of Kruskal's Algorithm is primarily determined by the time it takes to sort the edges and the time it takes to perform the union-find operations. The sorting of the edges takes $O(m \log m)$ time, where $m$ is the number of edges. The union-find operations can be performed in nearly constant time per operation, which leads to $O(m \alpha(n))$, where $\alpha(n)$ is the inverse Ackermann function, which grows very slowly and is practically considered constant. Therefore, the total running time of Kruskal's Algorithm is dominated by the sorting step, which leads to the correct answer being:

```
C. $O(m \log m)$ (m = edges, n = nodes)
```

Not the question you are looking for? Ask here!

Enter question by text

Enter question by image

Upgrade to Asksia Pro

Join a AskSia's Pro Plan, and get 24/7 AI tutoring for your reviews, assignments, quizzes and exam preps.

Unlimited chat query usages

Strong algorithms that better know you

Early access to new release features

Study Other Question