Understanding an upper bound in the analysis of Karger's algorithm

Question

I'm reading the wiki page of Karger's algorithm for a self-study of CLRS to get some and I'm confused by one of the bounds they have.

Here, under the section about finding all min cuts, they have this line $$(1-P(n))^{O(\log^{2} n)} \le (1-\frac{c}{\ln n})^{\frac{3}{c} \ln^{2} n}$$. I get that they are using the definition of big O to insert these constants, but what feels fishy to me is the choice for the constant in the exponent of $\log^{2} n$ of $\frac{3}{c}$. Why can't I just choose the coefficient to just be, $\frac{2}{c}$ and get a tighter bound? How do they know here that $\frac{3}{c}$ is the smallest coefficient that may be chosen?

I understand the rest of the argument, for the record (They're using $e^{x} \ge 1+x$)

Answer 1

$$(1-P(n))^{O(\log^{2} n)} \le (1-\frac{c}{\ln n})^{\frac{3}{c} \ln^{2} n}$$

First, to get a tighter bound, you should choose $\frac{4}{c}$ or larger, instead of $\frac{2}{c}$ or smaller.

In particular, the probability for $\frac{2}{c}$ is $$\textrm{Pr}[\textrm{miss any min-cut}] \le O(1).$$ This does not make sense for a probability value.

Second, the larger the chosen coefficient is, the higher the time complexity of the algorithm is (to achieve a tighter bound). That is, there is a trade-off.

Answer 2

The point here is that at the end the argument will use a union bound over all the $O(n^2)$ min cuts. So the failure probability for a single minimum cut needs to be $o(n^{-2})$ for this to give any useful information.

An alternative would be to try and replace the union bound with a more precise argument, but since a cycle has $\Omega(n^2)$ min cuts, this won't work in general.