Made Easy

Question

what will be the change in time when quick sort is used over the heap sort  to sort the edges in order to find the MST using kruskal algorithm...no of edges = 16

Answer 1

If we consider strictly Kruskal's algorithm , then we require sorting of edges and if we consider the worst case,

Quicksort will give = O(E²) [Considering the worst case of quicksort and the fact that we need sorting of edges in Kruskal's algo]

Heapsort will give = O(ElogE)

Substituting E = 16 we have ,

using quicksort we have : 16² = 256

and using heapsort =       16 log 16 = 64

Hence change in time = 256 - 64 = 192 time units

Comments

I am thinking why we are taking worst case TC of quick sort??

how it is O(E^2) can u plz explain

here we don't know how array will be divided by pivot and we know that TC of quick sort depends on partition of the array by pivot

TC of kruskal is O(ElogE) or O(ElogV)

---

Since in the question it is mentioned we use quicksort instead of heapsort so it is O(E²) since sort according to edge weights in kruskals ALGO first then we construct mst

---

@cse

since we dont know about the piovt position,,,better to go for worst case

---

ok..thanks:)