5. The wiki page presents pseudo-code for Karger's algorithm. For a graph has n nodes and m edges what is the computational complexity of Karger's algorithm in big-O terms? 

 O(n + m)
 O(n * log m)
 O(n * m)
 O(n ^ m)
 
 I got this exercise wrong. However, I believe that the second option is correct because the loop goes on while there are more than two vertices. While this is done, a merge goes on, which is log m. Correct?

yxu22 wrote:

Each merge would only reduce the number of edges by 1 not reduce half.

So the complexity is O( n * m)

Okay, but wouldn't reducing the edges by 1 be a constant process? Why is it O(n * m) instead of O(n)?

yxu22 wrote:

Because we need to merge until only two combined component left. 

So in the worst case (there would be only 1 cross edge), we need to merge m-1 times (initially we have m edges, we merge m-1 times, then we have 1 cross edge left.)

So generally speaking,    running time is O(n * m )

So for each iteration n, there is a merge that occurs yielding us O(n * m) complexity?