Worst case of randomized MST

In class we saw that the expected cost of the randomized MST algorithm is \(O(m+n)\). I want you to determine the worst-case cost.

Suppose the input to the randomized MST algorithm is a graph \(G\) with \(n\) nodes and \(m\) edges. We saw in Problem 58 examples of the worst-case for the Boruvka steps at the beginning.

After these Boruvka steps, the algorithm ends up with a subgraph \(G'\) with fewer nodes. The next step is choosing the subgraph \(H\) of \(G'\) for the first recursive call.

For your analysis, assume that exactly one half of the edges in \(G'\) are chosen to be in \(H\). It should not be too difficult to think of what the least-fortunate half of edges to include would be.

Based on this least-fortunate choice of \(H\), think about the MST of \(H\), which is recursively computed as \(F\). How many \(F\)-light edges will there be in \(G'\)?

Once you have the worst-case size of \(G''\) in terms of \(n\) and \(m\), you should be able to write down a recurrence for the worst-case cost of the algorithm. You should solve this recurrence to state what the worst-case cost is in terms of \(n\) and \(m\), but if you have the correct recurrence but just can't solve it, that's OK for this problem.