Question

What is the running time of Karger’s algorithm to find the minimum cut in a graph?

(a) O(E)

(b) O(|V|^2)

(c) O(V)

(d) O(|E|)

The question was asked in exam.

I'm obligated to ask this question of Minimum Cut in chapter Minimum Cut of Data Structures & Algorithms II

Answer 1

Correct answer is (b) O(|V|^2)

Easy explanation - The running time of Karger’s algorithm to find the minimum cut is mathematically found to be O(|V|^2).