Question

The running time of implementing naïve solution to min-cut problem is?

(a) O(N)

(b) O(N log N)

(c) O(log N)

(d) O(N^2)

This question was posed to me during an internship interview.

My doubt stems from Minimum Cut in division Minimum Cut of Data Structures & Algorithms II

Answer 1

The correct choice is (d) O(N^2)

For explanation: The running time of min-cut algorithm using naïve implementation is mathematically found to be O(N^2).