Problem 60

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

# Worst case of randomized MST

Due: April 5
Points: 3

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.