 The running time of fastmincut satisfies
with solution formula_65.To achieve error probability formula_66, the algorithm can be repeated formula_67 times, for an overall running time of formula_68.This is an order of magnitude improvement over Karger’s original algorithm.