V … number of vertices
E … number of edges

• Probability of success: `>= 1 - 1/V`
  • probability of not finding a minimum cut when the contraction algorithm is repeated `d = ` `((V),(2))``* ln V`  times: `<= [1 - 1 // ((V),(2))]^d <= 1 / e^(ln V) = 1 / V`
• Total running time: O(E·d) = O(E·V²·log V)
  • assuming edge contraction implemented in O(E)