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

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$)

• Hint: do away with the abuse of notation first, i.e. replace $O(\_)$ with a function $g \in O(\_)$ (symbolically). (I wonder if they actually need $\Omega$, but that may depend on $P$.) – Raphael Apr 15 '15 at 9:17

$$(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.
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.