Consider the following algorithm to compute the minimum -cost spanning tree of a connected weighted graph G. Algorithm RECURSIVEMST (G: weighted graph) Input: A simple connected weighted graph G = (V. E) with n vertices and m edges Assume that n is a power of two Output: A minimum spanning tree T for G if n = 2 then let u and v be the two vertices T + edge between u and v, if it exists (otherwise T+0) return T else partition V into Vi and V2 such that Vin V2 = 0, VI U V2 = V and V1] = |V2| let Ei edges incidents only on vertices of Vi let G1 + (V1, E) let Ti + recursivemst (G1) let E2 + edges incidents only on vertices of V2 let G2 + (V2, E2) let T2 + RECURSIVEMST(G2) let er minimum-weight edge among all the edges that have one endpoint in Vi and the other in V2 return Ti+e+T2 a) Write the recurrence relation for the time complexity of recursivemst
b) Determine the worst-case time complexity of recursivemst by solving the recurrence relation.
c) Is this algorithm faster than Kruskal's? d)Is the algorithm correct, i. e., does it always produce the minimum-cost spanning tree fir G? Give a counterexample if your answer is "No", a brief proof of correctness if your is "Yes".