Your friend proposes a divide-and-conquer approach to compute a minimum spanning

Question

Your friend proposes a divide-and-conquer approach to compute a minimum spanning tree of a connected graph G = (V, E). The helper function {G_1, G_2} = sub graphs (G) takes the graph G = (V, E) and partitions the vertices into two graphs G_1 = and G_2 = such that G_1 and G_2 are both connected and (V_1, E_1) and G_2 differ by at most 1. DC_MST(G = (V, E)): \ Assume that G is a connected graph \ Base cases: if IVI = 1: \ 1 vertex, no edges return NONE if IE| = 1: \ 1 edge, 2 vertices return E {G_1, G_2} = sub graphs(G) MST.1 = DC_MST(G_1) MST_2 = DC_MST(G_2) let e = the minimum-weight edge connecting G_1 and G_2 return [MST_1, e, MST_2] We'll start by analyzing the runtime of this algorithm. Assume that the sub graphs function runs in O(n + m) time, where n = |V| and m = |E|. We'll find it helpful to consider the performance of this algorithm in the best and worst cases. (a) The best case for this algorithm is a particular (simple and common) type of connected graph. What type of connected graph yields the best-case runtime? VERY briefly justify your answer. (b) What type of connected graph yields the worst-case runtime? VERY briefly justify your answer. (a) Give and briefly justify a good asymptotic lower bound on the best-case runtime of this algorithm in terms of n. (b) Give and briefly justify a good asymptotic upper bound on the worst-case runtime of this algorithm in terms of n. Does this algorithm always generate a minimum spanning tree? Justify your answer.

Explanation / Answer

1.

b)

We will get worst case complexity for the graphs with more number of edges as the comparisions

will be high in this case.

For Complete graph Kn we will get the worst case complexity as there will be more number of edges

n(n-1) /2 here we will have several possibiltes of subgraphs G1 and G2.

2.

b) Here in the algorithm we have two recursive function calls DC_MST(G_1) and DC_MST(G_2) also we have

a method to find subgraphs(G) which runs in o(n+m) complexity so the total recurrance relation for n

verticescan be written as below,

DC_MST(n) = 2 DC_MST(n/2) + o(n+m)

we know T(n) = 2T(n/2) + n on solving we get o(nlogn)

T(n) = 2T(n/2) + n

Next we will solve this recurrence relation. First we divide (2) by n:

(3) T(n) / n = T(n/2) / (n/2) + 1

n is a power of two, so we can write

(4) T(n/2) / (n/2) = T(n/4) / (n/4) +1

(5) T(n/4) / (n/4) = T(n/8) / (n/8) +1
(6) T(n/8) / (n/8) = T(n/16) / (n/16) +1
(7) ……
(8) T(2) / 2 = T(1) / 1 + 1

Now we add equations (3) through (8) : the sum of their left-hand sides
will be equal to the sum of their right-hand sides:

T(n) / n + T(n/2) / (n/2) + T(n/4) / (n/4) + … + T(2)/2 =

T(n/2) / (n/2) + T(n/4) / (n/4) + ….+ T(2) / 2 + T(1) / 1 + Logn

(Logn is the sum of 1s in the right-hand sides)

After crossing the equal term, we get

(9) T(n)/n = T(1)/1 + Logn

T(1) is 1, hence we obtain

(10) T(n) = n + nlogn = O(nlogn)

Hence the complexity is O(nlogn).

Hence complexity of above algortihm is (n+m) log(n+m).

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.